[LeetCode] 692. Top K Frequent Words

本文主要是介绍[LeetCode] 692. Top K Frequent Words，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/top-k-frequent-words/

题目大意

对于 string[] words，输出 出现频率前k高的 word，顺序 为 word 出现的频率 由高到低 ，频率相同的 word 按 字符排序。

思路

其实是对words中的所有word进行一个排序。
排序有两个规则：
1.word 在 words中出现的次数。
2.在相同 出现 次数的word中 按 字符 排序。

先对 words 使用 map 进行 计数。
然后 维护一个小堆，这个堆 的排序 和 题目要求排序 完全相反，大小为k。

然后将 map 中所有 entry往 小堆中放。

1. 若 小堆 没满，往进填。
2. 当 小堆 满了，将 堆顶 entry 和 entry 比较，若entry 大于 堆顶 时，将 堆顶 poll()，再添加 entry。

最后将 堆 中数据 倒序放入 res中，因为堆中排序 为倒序。

class Solution {public List<String> topKFrequent(String[] words, int k) {Map<String ,Integer> map = new HashMap<>();for(String word: words){map.put(word,map.getOrDefault(word,0)+1);}PriorityQueue<Map.Entry<String , Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){if(o1.getValue() == o2.getValue())return o2.getKey().compareTo(o1.getKey());return o1.getValue() - o2.getValue();}});for(Map.Entry<String,Integer> entry: map.entrySet()){if(pq.size()<k)pq.add(entry);else{if( (pq.peek().getValue() < entry.getValue()) || (pq.peek().getValue() == entry.getValue() &&entry.getKey().compareTo( pq.peek().getKey())<0)){pq.poll();pq.add(entry);}}}List<String> res = new LinkedList<>();int pqlen = pq.size();for(int i = 0; i < pqlen ; i++)res.add(0,pq.poll().getKey());return res;}
}

修改Comparator ，使更 规范

class Solution {public List<String> topKFrequent(String[] words, int k) {Map<String ,Integer> map = new HashMap<>();for(String word: words){map.put(word,map.getOrDefault(word,0)+1);}PriorityQueue<Map.Entry<String , Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<String,Integer>>(){public int compare(Map.Entry<String,Integer> o1,Map.Entry<String,Integer> o2){int res;if(o1.getValue() == o2.getValue())res = o1.getKey().compareTo(o2.getKey());elseres=o2.getValue() - o1.getValue();return -res;}});for(Map.Entry<String,Integer> entry: map.entrySet()){if(pq.size()<k)pq.add(entry);else{if( (pq.peek().getValue() < entry.getValue()) || (pq.peek().getValue() == entry.getValue() &&entry.getKey().compareTo( pq.peek().getKey())<0)){pq.poll();pq.add(entry);}}}List<String> res = new LinkedList<>();int pqlen = pq.size();for(int i = 0; i < pqlen ; i++)res.add(0,pq.poll().getKey());return res;}
}

注意 语言的使用
note：

1. PriorityQueue 中 new Comparator(){
   public int compare(T o1, To2){
   }
   }

2. map 中排序 ，使用 entry 。 PriorityQueue<Map.Entry<String,Integer>>

3. qp.add(int index, ele)

4. pq.poll()

这篇关于[LeetCode] 692. Top K Frequent Words的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---