-
Notifications
You must be signed in to change notification settings - Fork 1
/
LeetCode-692-Top-K-Frequent-Words.java
110 lines (91 loc) · 3.8 KB
/
LeetCode-692-Top-K-Frequent-Words.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
class Solution {
// 1. HashMap frequency + bucket sort
/*
Time O(N)
Space O(N)
https://leetcode.com/problems/top-k-frequent-words/discuss/309702/My-simple-Java-solution-using-Bucket
*/
// public List<String> topKFrequent(String[] words, int k) {
// HashMap<String, Integer> frequencyMap = new HashMap<>();
// for (String w : words) frequencyMap.put(w, frequencyMap.getOrDefault(w, 0) + 1);
// List<String>[] bucket = new List[words.length + 1]; // index is frequency
// for (String w : frequencyMap.keySet()) {
// int frequency = frequencyMap.get(w);
// if (bucket[frequency] == null) bucket[frequency] = new ArrayList<>();
// // {love=2, coding=1, i=2, leetcode=1}
// bucket[frequency].add(w);
// }
// System.out.println(frequencyMap.toString());
// System.out.println(Arrays.toString(bucket));
// List<String> res = new ArrayList<>();
// for (int i = bucket.length - 1; i >= 0; i--) {
// if (bucket[i] == null) continue;
// Collections.sort(bucket[i]);
// for (String w : bucket[i]) {
// if (res.size() < k) {
// res.add(w);
// }
// }
// }
// return res;
// }
// 2. HashMap frequency + PriorityQueue frequency
/*
https://leetcode.com/problems/top-k-frequent-words/discuss/302048/Plain-and-simple
*/
// public List<String> topKFrequent(String[] words, int k) {
// // Arrays.sort(words, Collections.reverseOrder());
// // build frequency map
// HashMap<String, Integer> map = new HashMap<>();
// for (String w : words) map.put(w, map.getOrDefault(w, 0) + 1);
// // build frequency priority queue - Max Heap
// // be careful, here we must make the pq to be descending. If the frequency is the same, then alphabet order
// PriorityQueue<String> queue = new PriorityQueue(new Comparator<String>(){
// public int compare(String s1, String s2) {
// if (map.get(s1) == map.get(s2)) return s1.compareTo(s2);
// return map.get(s2) - map.get(s1);
// }
// });
// for (String w : map.keySet()) queue.offer(w);
// // get result from frequency pq
// List<String> res = new ArrayList<>();
// for (int i = 0; i < k; i++) res.add(queue.poll());
// return res;
// }
// Max-Heap solution using a self-defined Pair and PairComparator.
/*
https://leetcode.com/problems/top-k-frequent-words/discuss/298549/Java-Heap-6-ms-faster-than-98.95-38.1-MB-less-than-93.80
*/
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> cnts = new HashMap<>();
for (String word : words) {
cnts.put(word, cnts.getOrDefault(word, 0) + 1);
}
PriorityQueue<Pair> pq = new PriorityQueue<>(new PairComparator());
for (String key : cnts.keySet()) {
pq.offer(new Pair(key, cnts.get(key)));
}
List<String> res = new ArrayList<>();
for (int i = 0; i < k; ++i) {
res.add(pq.poll().word);
}
return res;
}
private class PairComparator implements Comparator<Pair> {
public int compare(Pair a, Pair b) {
if (a.cnt == b.cnt) {
return a.word.compareTo(b.word);
} else {
return b.cnt - a.cnt;
}
}
}
private class Pair {
String word;
int cnt;
Pair(String word, int cnt) {
this.word = word;
this.cnt = cnt;
}
}
}