[LeetCode] 692. Top K Frequent Words

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:
Input: words = [“i”,”love”,”leetcode”,”i”,”love”,”coding”], k = 2
Output: [“i”,”love”]
Explanation: “i” and “love” are the two most frequent words.
Note that “i” comes before “love” due to a lower alphabetical order.

Example 2:
Input: words = [“the”,”day”,”is”,”sunny”,”the”,”the”,”the”,”sunny”,”is”,”is”], k = 4
Output: [“the”,”is”,”sunny”,”day”]
Explanation: “the”, “is”, “sunny” and “day” are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

Constraints:
1 <= words.length <= 500
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
k is in the range [1, The number of unique words[i]]

Follow-up: Could you solve it in O(n log(k)) time and O(n) extra space?

前K个高频单词。

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/top-k-frequent-words
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路 - 最小堆

因为是前 K 个 XX 的题型所以思路不是优先队列就是 bucket sort。本题是用到 heap/priority queue。先用 hashmap 存每个单词和他们出现的频率，然后用 pq 创建一个最小堆，并且做一个 comparator 比较单词出现的频率，如果两个单词的出现频率相同，则比较两个单词的字典序，字典序小的在前，否则就按照这两个单词的出现频率从大到小排序。

这样排序，频率小的单词更靠近堆顶，字典序大的单词更靠近堆顶，所以弹出的时候，需要把 list 反转一下。

复杂度

时间O(nlogk)
空间O(k)

代码

Java实现

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }

        // 小频率在堆顶 → 被先 poll 掉 → 最后留下的是频率大的
        // 如果频率相同，我们要留下字典序小的，所以堆顶是字典序大的
        PriorityQueue<String> queue = new PriorityQueue<>((a, b) -> {
            int freq1 = map.get(a);
            int freq2 = map.get(b);
            if (freq1 != freq2) {
                return freq1 - freq2;
            } else {
                return b.compareTo(a);
            }
        });
        for (String key : map.keySet()) {
            queue.offer(key);
            if (queue.size() > k) {
                queue.poll();
            }
        }

        List<String> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            res.add(queue.poll());
        }
        Collections.reverse(res);
        return res;
    }
}
// min heap