692. 前K个高频单词 - 力扣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].length 10 * words[i] 由小写英文字母组成。 * k 的取值范围是 [1, 不同 words[i] 的数量] 进阶尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。https://leetcode.cn/problems/top-k-frequent-words/题目描述给定一个单词列表words和一个整数k返回前k个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率按字典升序排序。示例 1 输入words [i,love,leetcode,i,love,coding], k 2输出[i,love]解析i、love 都出现 2 次频次相同按字典序i排在love前面。题目核心两点按出现频次降序频次相等按字典序升序。解题思路哈希统计 优先队列 (小根堆) topK哈希表统计频次unordered_mapstring, int遍历所有单词统计每个单词出现次数。小根堆筛选 Top‑K求前 K 个最大元素使用小根堆堆中最多保存 k 个元素堆顶维护当前 k 个里面 “最差” 元素当堆大小 k直接弹出堆顶淘汰掉最差⚠️重点自定义比较器处理双重排序规则频次、字典序。结果倒序输出小根堆堆顶是 k 个里面频次最低的从后往前填充结果数组得到从高频到低频的答案。topK 口诀求前 K 大用小根堆求前 K 小用大根堆。堆顶存放待淘汰元素容量超限直接 pop 堆顶。⚠️Cpriority_queue底层是大根堆自定义cmp比较器有特殊规则cmp(a,b)返回true代表a 优先级低于 bb 放到堆顶。class Solution { public: typedef pairstring,int PSI; struct cmp{ bool operator()(const PSIa,const PSIb) { if(a.secondb.second) { return a.firstb.first; } return a.secondb.second; } }; vectorstring topKFrequent(vectorstring words, int k) { unordered_mapstring,inthash; for(auto e:words) hash[e]; priority_queuePSI,vectorPSI,cmpheap; for(auto e:hash) { heap.push(e); if(heap.size()k) heap.pop(); } vectorstring ret(k); for(int ik-1;i0;i--) { ret[i]heap.top().first; heap.pop(); } return ret; } };
