leetcode347. 前 K 个高频元素

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目最终需要返回的是前 kk 个频率最大的元素，可以想到借助堆这种数据结构，对于 kk 频率之后的元素不用再去处理，进一步优化时间复杂度。

具体操作为：

借助哈希表来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率
维护一个元素数目为 k 的最小堆
每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较
如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中
最终，堆中的 k 个元素即为前 k个高频元素

class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
//建立优先队列
struct cmp
{
bool operator()(const pair<int,int>& p1,const pair<int,int>& p2)
{
return p1.second > p2.second;//频次最高的优先级低，放在队尾哈
}
};
vector<int>res;
unordered_map<int,int>hashmap;
priority_queue<pair<int,int>,vector<pair<int,int>>,cmp>pr_qq; //建立哈希映射<元素值，出现频次>
for(int i=;i<nums.size();i++)
{
if(hashmap.count(nums[i])) hashmap[nums[i]]++;
else
hashmap.insert(make_pair(nums[i],));
}
auto it=hashmap.begin();
for(int i=;it!=hashmap.end()&&i<k;it++,i++)
{
pr_qq.push(make_pair(it->first,it->second));
} for(;it!=hashmap.end();it++)
{
pr_qq.push(make_pair(it->first,it->second));
pr_qq.pop();//弹出去现在频次最低的，也即是队列首部的
}
while(!pr_qq.empty())
{
res.push_back(pr_qq.top().first);
pr_qq.pop();
}
return res; }
};