Leetcode 692. 前K个高频单词（哈希表或优先队列）

秒速五厘米 2024-05-08 06:24 7阅读 0赞

##### 题目 #####

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

**示例 1：**

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
    输出: ["i", "love"]
    解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
        注意，按字母顺序 "i" 在 "love" 之前。

**示例 2：**

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
    输出: ["the", "is", "sunny", "day"]
    解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
        出现次数依次为 4, 3, 2 和 1 次。

**注意：**

*  假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
 *  输入的单词均由小写字母组成。

##### 思路一 #####

可以把所有的字符串出现次数放到一个map中，把字符串放到一个数组中，然后对这个数组进行排序，最后输出前k个元素

##### 代码 #####

class Solution {
        
        public List<String> topKFrequent(String[] words, int k) {
        
            Map<String, Integer> cnt = new HashMap<String, Integer>();
            //为所有的单词计数放入map中
            for(String word : words) cnt.put(word, cnt.getOrDefault(word, 0) + 1);
            List<String> rec = new ArrayList<String>();
            //取所有的key值放入数组中
            for(Map.Entry<String, Integer> entry : cnt.entrySet()) rec.add(entry.getKey());
            //自定义排序：当个数相同时，按照字母序列排序
            Collections.sort(rec, new Comparator<String>(){
        
                public int compare(String word1, String word2){
        
                    return cnt.get(word1) == cnt.get(word2) ? word1.compareTo(word2) : cnt.get(word2) - cnt.get(word1);
                }
            });
            //返回前k个数组元素
            return rec.subList(0, k);
        }
    }

##### 思路二 #####

将键值对放入优先队列中，此时这个优先队列的底层为小顶堆，当队列中元素的个数大于k时，将队列首元素弹出，最后队列中就会只有前K个最大的元素

##### 代码 #####

class Solution {
        
        public List<String> topKFrequent(String[] words, int k) {
        
            Map<String, Integer> cnt = new HashMap<String, Integer>();
            for(String word : words) cnt.put(word, cnt.getOrDefault(word, 0) + 1);
            PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(new Comparator<Map.Entry<String, Integer>>(){
        
                //注意这个优先队列是小顶堆
                public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2) {
        
                    return entry1.getValue() == entry2.getValue() ? entry2.getKey().compareTo(entry1.getKey()) : entry1.getValue() - entry2.getValue();
                }
            });
            for(Map.Entry<String, Integer> entry : cnt.entrySet()) {
        
                pq.offer(entry);
                //插入一个新元素后若元素个数大于k，需要弹出队列的最小元素
                if(pq.size() > k) pq.poll();
            }
            List<String> ret = new ArrayList<String>();
            //当队列非空时，依次取出元素放入数组中
            while(!pq.isEmpty()) ret.add(pq.poll().getKey());
            //翻转数组
            Collections.reverse(ret);
            return ret;
        }
    }

##### 关于排序的一些问题 #####

*  当Comparator的compare方法返回负值和零时，不会交换两个元素；当返回正数时，会交换两个元素；
 *  在写的时候，假定a，b的位置是排好序的，可以一直返回为负的表达式，这样a，b位置就不会交换了；
 *  对于字符串的compareTo函数，如a.compareTo(b)，当a的字母序大于b的字母序时返回负值，不交换二者的位置；

**参考链接：** https://blog.csdn.net/weixin\_44998686/article/details/109550175