这段代码实现的是:在一个整数数组中,找出出现频率最高的前 k 个元素。也就是说,你想找的是出现次数最多的 k 个数字。
class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> mp;priority_queue<pair<int, int>> pq;vector<int> res;for(int num : nums) {mp[num]++;}for(auto it = mp.begin(); it != mp.end(); it++) {pq.push(pair<int, int>(it->second, it->first));}while(k--) {res.push_back(pq.top().second);pq.pop();}return res;}
};
✅ 一、题目简述
输入:nums = [1,1,1,2,2,3], k = 2
输出:[1, 2]
因为 1 出现了 3 次,2 出现了 2 次,是前两个出现次数最多的。
✅ 二、算法思路详解
你采用了哈希表 + 大顶堆的做法,时间复杂度是 O(n log n),思路清晰、非常经典。
1. 使用 unordered_map 统计频率:
unordered_map<int, int> mp;
for (int num : nums) {mp[num]++;
}
这一步把所有数字出现的频率都存入哈希表 mp,键是数字,值是出现次数。
以 nums = [1,1,1,2,2,3] 为例,map 最终为:
{1: 3,2: 2,3: 1
}
2. 使用 priority_queue 构建最大堆(默认大顶堆):
priority_queue<pair<int, int>> pq;
for (auto it = mp.begin(); it != mp.end(); ++it) {pq.push({it->second, it->first});
}
将频率(it->second)作为堆的优先级,pair 的第一个元素作为排序依据。
这样堆顶就是当前频率最大的数字。
3. 取出前 k 个频率最高的元素:
while (k--) {res.push_back(pq.top().second);pq.pop();
}
• 每次从堆顶取出元素,把数字加入结果数组 res
• 取出 k 次,就得到了频率最高的前 k 个元素
✅ 三、时间复杂度分析
步骤 | 时间复杂度 |
---|---|
哈希统计频率 | O(n) |
构建最大堆(n 个元素) | O(n log n) |
取出前 k 个元素 | O(k log n) |
总复杂度 | O(n log n),空间 O(n) |
✅ 四、举个例子运行一下
输入:
nums = [4, 1, 1, 2, 2, 3, 3, 3]
k = 2
第一步统计频率:
mp = {1: 2,2: 2,3: 3,4: 1
}
第二步建堆:
堆内容为(按 pair<int, int> 构建,自动按频率排序):
(3, 3)
(2, 2)
(2, 1)
(1, 4)
第三步取前 2 个:
• 第一次弹出 (3, 3) → 加入结果:3
• 第二次弹出 (2, 2) 或 (2, 1) → 加入结果:2(或 1)
返回结果可能是 [3, 2] 或 [3, 1],顺序不重要
✅ 总结
步骤 | 技术细节 |
---|---|
频率统计 | 使用哈希表 |
快速找最大频率值 | 使用大顶堆 |
保证前 k 高频 | 每次取堆顶 k 次 |
详细讲一下这句 C++ 容器的用法:
priority_queue<pair<int, int>> pq;
这是在声明一个 大顶堆(最大优先队列),元素类型是 pair<int, int>,即两个整数的组合。
✅ 一、什么是 priority_queue?
priority_queue 是 C++ STL 中的一个容器适配器,默认是一个大顶堆。也就是说,堆顶(top())总是最大的那个元素。
✅ 二、pair 的排序规则(默认)
当你放入的是 pair<int, int> 类型时,它默认使用 字典序排序,也就是比较:
• 先比第一个元素(first),大的优先
• 如果第一个相等,再比第二个元素(second)
🌰 例子:
priority_queue<pair<int, int>> pq;
pq.push({3, 100});
pq.push({2, 200});
pq.push({3, 50});
堆的排序顺序是:
• {3, 100}(最大,排在堆顶)
• {3, 50}
• {2, 200}(最小)
✅ 三、使用方法总结
1. 声明
priority_queue<pair<int, int>> pq;
2. 插入元素
pq.push({次数, 元素值});
3. 取堆顶
pq.top(); // 返回 pair,最多的那个(按 pair 排序规则)
4. 删除堆顶
pq.pop();
5. 判断是否为空
pq.empty();
✅ 四、应用场景(比如频率统计)
在你前面这题:
// 频率作为 first,元素值作为 second
pq.push({it->second, it->first});
也就是 pq 中每个元素是 {频率, 数字},这样:
• top() 总是出现次数最多的数字
• 弹出 k 次,就得到了 top-k frequent elements
✅ 五、自定义排序(扩展)
如果你想改成小顶堆(比如为了保留最小的前 K 个),可以这么写:
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
这里使用了第三个模板参数 greater<>,改成最小堆。
🧠 总结小抄
声明方式 | 类型 | 默认顺序 |
---|---|---|
priority_queue<int> | 整数堆 | 最大值优先 |
priority_queue<pair<int,int>> | pair堆 | 按 first 降序,再按 second 降序 |
priority_queue<..., greater<>> | 任意类型 | 最小值优先 |