题目

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例：

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

输入: ["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 个高频单词（大小比较先比单词出现次数，如果相等则比较字典序） ```cpp struct cmp { bool operator() (pair
pair1, pair
pair2) {
```
 return pair1.second > pair2.second ||
         (pair1.second == pair2.second && pair1.first < pair2.first);
```
} };

class Solution { public: vector topKFrequent(vector& words, int k) { // 哈希表：统计每个单词出现的次数 unordered_map wordFreqMap; for(int i = 0; i < words.size(); ++i) ++wordFreqMap[words[i]];

    // 优先队列（小根堆），维护前 k 个高频单词
    priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> minHeap;
    int i = 0;
    for(auto it = wordFreqMap.begin(); it != wordFreqMap.end(); ++it, ++i)
    {
        if(i < k)
            minHeap.push(make_pair(it->first, it->second));
        else
        {
            if(it->second > minHeap.top().second ||
                (it->second == minHeap.top().second && it->first < minHeap.top().first))
            {
                minHeap.pop();
                minHeap.push(make_pair(it->first, it->second));
            }
        }
    }

    // 将优先队列中的 k 个单词存储到结果数组中
    vector<string> result(k);
    for(int i = k - 1; i >= 0; --i)
    {
        result[i] = minHeap.top().first;
        minHeap.pop();
    }
    return result;
}

};

复杂度分析：设单词列表 words 长为 n，包含 m 种不同的单词，每个单词的平均长度为 s，要取前 k 个高频单词

- 时间复杂度 O(n * s + m * s logk)：
   - 需要 n * s 的时间将单词列表中的所有 word 插入到哈希表
   - 优先队列的最大长度为 k，因此每次插入的时间复杂度 O(s logk)，最多需要插入 m 次
- 空间复杂度 O(s * (m + k))：
   - 哈希表空间复杂度 O(s * m)
   - 优先队列空间复杂度 O(s * k)

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 64.33% 的用户内存消耗：12.2 MB, 在所有 C++ 提交中击败了 60.30% 的用户 ```

hot 100

[中等] 692. 前K个高频单词

题目

解答 & 代码