算法日常・每日刷题--＜优先级队列＞3

692. 前K个高频单词 - 力扣（LeetCode）692. 前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前面。

题目核心两点：

1. 按出现频次降序；
2. 频次相等，按字典序升序。

解题思路：哈希统计 + 优先队列 (小根堆) topK

1. 哈希表统计频次：unordered_map<string, int>遍历所有单词，统计每个单词出现次数。
2. 小根堆筛选 Top‑K：
   • 求前 K 个最大元素，使用小根堆，堆中最多保存 k 个元素；
   • 堆顶维护当前 k 个里面 “最差” 元素，当堆大小 > k，直接弹出堆顶，淘汰掉最差；
   • ⚠️重点：自定义比较器，处理双重排序规则（频次、字典序）。
3. 结果倒序输出：小根堆堆顶是 k 个里面频次最低的，从后往前填充结果数组，得到从高频到低频的答案。

💡topK 口诀：求前 K 大，用小根堆；求前 K 小，用大根堆。堆顶存放待淘汰元素，容量超限直接 pop 堆顶。

⚠️C++priority_queue底层是大根堆，自定义cmp比较器有特殊规则：cmp(a,b)返回true代表：a 优先级低于 b，b 放到堆顶。

class Solution { public: typedef pair<string,int> PSI; struct cmp{ bool operator()(const PSI&a,const PSI&b) { if(a.second==b.second) { return a.first<b.first; } return a.second>b.second; } }; vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string,int>hash; for(auto& e:words) hash[e]++; priority_queue<PSI,vector<PSI>,cmp>heap; for(auto &e:hash) { heap.push(e); if(heap.size()>k) heap.pop(); } vector<string> ret(k); for(int i=k-1;i>=0;i--) { ret[i]=heap.top().first; heap.pop(); } return ret; } };