前K个高频单词

力扣 692. 前K个高频单词

题目说明

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

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
提示：
- 假定 k 总为有效值， 1 ≤ 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 次。

笔者理解

此题是一道哈希算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题首先需要将各个单词出现的频次计算出来，然后再对得出的结果进行排序提取，在这里我们采用哈希表和优先队列来求解，让我们来看看具体如何实现的吧。

实现

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>> queue = new PriorityQueue<>(
                (entry1, entry2) ->
                        // 如果两个单词出现的频次相同，按字母顺序排序
                        entry1.getValue() == entry2.getValue() ? entry2.getKey().compareTo(entry1.getKey())
                        // 否则按照两个单词出现的频次排序
                        : entry1.getValue() - entry2.getValue());

        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            queue.offer(entry);

            // 将优先队列的数目维持在k个
            if (queue.size() > k) {
                queue.poll();
            }
        }

        List<String> result = new ArrayList<>();

        while (!queue.isEmpty()) {
            result.add(queue.poll().getKey());
        }

        // 将优先队列(小顶堆)得出的结果逆序为按照频次 降序 的结果集
        Collections.reverse(result);

        return result;
    }