《LeetCode刷题计划》前K个高频单词

小鱼儿 2023-09-28 05:14 139阅读 0赞

![6c98bb9b8e3f47fcb960fc6046fec693.png][]

> 一开始的思路：
> 
> **将所有的单词建立大根堆（按出现的次数完成大根堆的构建(如果出现次数相同，按字典顺序排序)然后按顺序弹出k个元素**

>     class Solution {
>         public List<String> topKFrequent(String[] words, int k) {
>             Map<String, Integer> map = new HashMap<>();
>             for (String word : words) {
>                 if (map.containsKey(word)) {
>                     int val = map.get(word); // 注意我们的map.get返回的是Integer引用类型，在这个过程发生了自动拆箱
>                     map.put(word, val + 1);
>                 }
>                 else {
>                     map.put(word, 1);
>                 }
>             }
>             // 程序到了这，我们把单词以及单词出现的次数储存到了Map中
>             
>             // 接下来遍历单词列表中所有的key-value映射关系，储存到PriorityQueue中（建立大根堆）
>             CountCmp countCmp = new CountCmp();
>             PriorityQueue<Map.Entry<String, Integer>> priorityQueue = new PriorityQueue<>(countCmp);
>             Set set = map.entrySet(); // 返回所有的 key-value 映射关系, 返回值的类型为Set<Map.Entry<String, Integer>>
>             for (Map.Entry<String, Integer> entry : map.entrySet()) {
>                 priorityQueue.offer(entry);
>             }
>             
>             // 弹出k个堆顶元素
>            List<String> ret = new ArrayList<>();
>             for (int i = 0; i < k; ++i) {
>                 ret.add(priorityQueue.poll().getKey());
>             }
>             return ret;
>         }
>     }
>         
>        // 自定义了一个比较器对象，按出现的次数完成大根堆的构建(如果出现次数相同，按字典顺序排序)
>     class CountCmp implements Comparator<Map.Entry<String, Integer> >{
>         @Override
>         public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
>             if (o1.getValue().equals(o2.getValue())) {
>                 return o1.getKey().compareTo(o2.getKey());
>             }
>             else{
>                 return o2.getValue().compareTo(o1.getValue()); // 因为这里获取的是Integer引用类型，所以用compareTo来比较
>             }
>         }
>     }

改进后的思路

> 对于前 k 大或前 k 小这类问题，有一个通用的解法：优先队列。优先队列可以在 O(logn) 的时间内完成插入或删除元素的操作（其中 n 为优先队列的大小），并可以O(1) 地查询优先队列顶端元素。
> 
> **在本题中，我们可以创建一个小根优先队列（顾名思义，就是优先队列顶端元素是最小元素的优先队列）。我们将每一个字符串插入到优先队列中，如果优先队列的大小超过了 k，那么我们就将优先队列顶端元素弹出。这样最终优先队列中剩下的 k 个元素就是前 k 个出现次数最多的单词。**

>     class Solution {
>         public static List<String> topKFrequent(String[] words, int k) {
>             //1、统计单词出现的次数  key:单词   val: 次数
>             Map<String,Integer> map = new HashMap<>();
>             for (String word : words) {
>                 if(map.get(word) == null) {
>                     map.put(word,1);
>                 }else {
>                     int val = map.get(word);
>                     map.put(word,val+1);
>                 }
>             }
>             //2、建立大小为k的 小根堆
>             PriorityQueue<Map.Entry<String,Integer>> minHeap =
>                     new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
>                 @Override
>                 public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
>                     //比较频率
>                     if(o1.getValue().compareTo(o2.getValue()) == 0) {
>                         //做一个转换
>                         return o2.getKey().compareTo(o1.getKey());
>                     }
>                     //return o1.getValue()-o2.getValue();
>                     return o1.getValue().compareTo(o2.getValue());
>                 }
>             });
>     
>             //遍历map
>             for (Map.Entry<String,Integer> entry : map.entrySet()) {
>                 if(minHeap.size() < k) {
>                     minHeap.offer(entry);
>                 }else {
>                     //此时需要和堆顶元素去比较
>                     Map.Entry<String,Integer> top = minHeap.peek();
>                     Integer val = top.getValue();
>                     // entry是当前的元素
>                     if(val.compareTo(entry.getValue())<0) {
>                         minHeap.poll();
>                         minHeap.offer(entry);
>                     }else if(val.compareTo(entry.getValue()) == 0) {
>                         String key = top.getKey();
>                         if(key.compareTo(entry.getKey()) > 0) {
>                             minHeap.poll();
>                             minHeap.offer(entry);
>                         }
>                     }
>                 }
>             }
>             List<String> list = new ArrayList<>();
>             for (int i = 0; i < k; i++) {
>                 String key = minHeap.poll().getKey();
>                 list.add(key);
>             }
>             Collections.reverse(list);
>             return list;
>         }
>     }

[6c98bb9b8e3f47fcb960fc6046fec693.png]: https://img-blog.csdnimg.cn/6c98bb9b8e3f47fcb960fc6046fec693.png