Top K Frequently Mentioned Keywords
原题地址
给定一些有若干单词组成的评论和一些关键词，求问最热门的K个关键词，不区分大小写，出现次数相同则按照字母顺序排序
很标准的哈希打表问题，本题一个容易忽视的点是在同一个评论中的关键词出现多次也只能算一次，这个很多原文下面的题解都没有注意到。
另外就是分开评论中各个词时，应该使用split("\\W")，因为可能出现逗号句号等非空白符。
遍历每个评论的所有单词，如果关键词在其中则累积。
最后放入一个大顶堆（优先队列），输出堆顶的K个值即可
本题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| private static List<String> getTopKFrequent(int k, String[] keywords, String[] reviews) {
Map<String, Integer> count = new HashMap<>();
for (String review : reviews) {
Set<String> curWords = new HashSet<>(Arrays.asList(review.toLowerCase().split("\\W")));
for (String word : keywords) {
if (curWords.contains(word)) {
count.merge(word, 1, Integer::sum);
}
}
}
System.out.println(count);
Queue<Map.Entry<String, Integer>> maxHeap = new PriorityQueue<>((a, b) -> a.getValue().equals(b.getValue()) ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue());
maxHeap.addAll(count.entrySet());
List<String> ans = new ArrayList<>();
while (!maxHeap.isEmpty() && k-- > 0) {
ans.add(maxHeap.poll().getKey());
}
return ans;
}
|
Leetcode692 Top K Frequent Words
原文地址
几乎一样，更直接
本题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> count = new HashMap<>();
for (String word : words) {
count.merge(word, 1, Integer::sum);
}
Queue<Map.Entry<String, Integer>> maxHeap = new PriorityQueue<>((a, b) -> a.getValue().equals(b.getValue()) ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue());
maxHeap.addAll(count.entrySet());
List<String> ans = new ArrayList<>();
while (!maxHeap.isEmpty() && k-- > 0) {
ans.add(maxHeap.poll().getKey());
}
return ans;
}
|
Leetcode347 Top K Frequent Elements
原文地址
元素从字符串变为了整数，其他一样
本题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.merge(num, 1, Integer::sum);
}
Queue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(count::get));
for (int n : count.keySet()) {
heap.add(n);
if (heap.size() > k) heap.poll();
}
int[] top = new int[k];
for(int i=k-1; i>=0; --i) {
top[i] = heap.poll();
}
return top;
}
|
