58-Map和Set练习-LeetCode692前k个高频单词

题目

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

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

示例 1：

输入: words = ["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 次。

注意：

    1 <= words.length <= 500
    1 <= words[i] <= 10
    words[i] 由小写英文字母组成。
    k 的取值范围是 [1, 不同 words[i] 的数量]

进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

---

思路：

前k个高频元素

找大用小。

1. 用Map扫描集合，将每个单词及出现的频率存入Map中。
2. 声明一个基于最小堆的优先级队列，传入比较器。（题目要求：默认按出现频次大小排序，频次相同再按字典排序。用String默认的compareTo方法即可；String默认实现了Comparable，基于字母的字典序比较）
3. 依次出队列，找到前k个高频单词。

---

代码

class Solution {public List<String> topKFrequent(String[] words, int k) {//1.扫描原数组，将每个单词及出现的次数存储在Map中Map<String, Integer> cnt = new HashMap<String, Integer>();for (String word : words) {cnt.put(word, cnt.getOrDefault(word, 0) + 1);}//2.扫描Map集合，将前k个出现频次最高的入优先级队列（最小堆）//向优先级队列中传入一个比较器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();}});//将每一个字符串插入到优先队列中，如果优先队列的大小超过了 k，那么就将优先队列顶端元素弹出。这样最终优先队列中剩下的 k 个元素就是前 k 个出现次数最多的单词。for (Map.Entry<String, Integer> entry : cnt.entrySet()) {pq.offer(entry);if (pq.size() > k) {pq.poll();}}//3.依次出队列，找到前k个高频单词。List<String> ret = new ArrayList<String>();//取大用小，每次从最小堆中堆顶取，得到的前k个高频单词的频率是从小到大的while (!pq.isEmpty()) {ret.add(pq.poll().getKey());}//将ret集合进行反转，这样就实现找到前k个高频单词的频率是从大到小的Collections.reverse(ret);return ret;}
}