-
Notifications
You must be signed in to change notification settings - Fork 8
/
TopKFrequentWords.java
112 lines (91 loc) · 3.5 KB
/
TopKFrequentWords.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
111
112
package hashtable;
// Source : https://leetcode.com/problems/top-k-frequent-words/
// Id : 692
// Author : Fanlu Hai | https://github.com/Fanlu91/FanluLeetcode
// Topic : Hashtable
// Date : 2019-04-23
// Other : I used PriorityQueue which I suppose should be some other data structure implemented by myself.
// Tips :
// Result : 99.50% 89.29%
import java.util.*;
public class TopKFrequentWords {
Map<String, Integer> countMap = new HashMap<>();
//99.50% 89.29%
public List<String> topKFrequent(String[] words, int k) {
for (String word : words) {
countMap.put(word, countMap.getOrDefault(word, 0) + 1);
}
PriorityQueue<String> queue = new PriorityQueue<>(words.length, new StringComparator());
for (String word : countMap.keySet()) {
queue.add(word);
}
List<String> list = new ArrayList<>();
for (int i = 0; i < k; i++) {
list.add(queue.poll());
}
return list;
}
//99.50% 89.29%
public List<String> topKFrequentOriginal(String[] words, int k) {
for (String word : words) {
if (countMap.containsKey(word)) {
countMap.put(word, (countMap.get(word) + 1));
} else {
countMap.put(word, 1);
}
}
PriorityQueue<String> queue = new PriorityQueue<>(words.length, new StringComparator());
for (String word : countMap.keySet()) {
queue.add(word);
}
List<String> list = new ArrayList<>();
for (int i = 0; i < k; i++) {
list.add(queue.poll());
}
return list;
}
//53.29% 100%
public List<String> topKFrequentWithExperiment(String[] words, int k) {
for (String word : words) {
// if below code is used 53.29% 39.95%
// if (countMap.containsKey(word)) {
// countMap.put(word, (countMap.get(word) + 1));
// } else {
// countMap.put(word, 1);
// }
// use getOrDefault instead of code above
countMap.put(word, countMap.getOrDefault(word, 0) + 1);
}
// PriorityQueue<String> queue = new PriorityQueue<>(words.length, new StringComparator());
// use lambda instead of inner class
// it seems lambda can save some space but also slow down the program.
PriorityQueue<String> queue = new PriorityQueue<String>(
(w1, w2) -> countMap.get(w1).equals(countMap.get(w2)) ?
w1.compareTo(w2) : countMap.get(w2) - countMap.get(w1));
for (String word : countMap.keySet()) {
queue.add(word);
}
List<String> list = new ArrayList<>();
for (int i = 0; i < k; i++) {
list.add(queue.poll());
}
return list;
}
class StringComparator implements Comparator<String> {
public int compare(String s1, String s2) {
if (countMap.get(s1) < countMap.get(s2))
return 1;
else if (countMap.get(s1) > countMap.get(s2))
return -1;
return s1.compareTo(s2);
}
}
public static void main(String[] args) {
TopKFrequentWords topKFrequentWords = new TopKFrequentWords();
String[] list = new String[]{"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
List<String> result = topKFrequentWords.topKFrequent(list, 2);
for (String s : result) {
System.out.println(s);
}
}
}