【力扣-优先队列】前 K 个高频元素
题目描述
中等
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]示例 2:
输入: nums = [1], k = 1
输出: [1]提示：
1 <= nums.length <= 10<sup>5</sup>k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶： 你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
解题思路
先用哈希表记录每个元素出现的次数。
然后你可以直接按照出现次序排序，但是这样排序最快要O(nlogn),可以进一步优化，用优先队列来做：
先开一个小根堆，让上面计算出的元素和频次依次入队。如果队列中元素数量小于k个，新元素直接入队，如果已有k个，则让队头元素频次（队中最小）和新元素的出现频次比较，如果新元素的出现频次小于队头元素频次，说明队列中k个元素频次均大于当前新元素，所以舍弃该新元素。反之如果新元素频次大于队头元素频次，则队头出队，新元素插入。最终队列中的k个元素就是出现频次最高的k个元素了。
代码
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> dp;
for(auto num : nums){
dp[num]++;
}
//自定义小根堆比较器
auto cmp = [](auto p1, auto p2)->bool{return p1.second > p2.second;};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp) > pque(cmp);
for(auto pa : dp){
if(pque.size() < k){
pque.push(pa);
}
else{
if(pque.top().second < pa.second){
pque.pop();
pque.push(pa);
}
}
}
vector<int> topk;
while(pque.empty() == false){
topk.push_back(pque.top().first);
pque.pop();
}
return topk;
}时间复杂度：O(nlogk) 空间复杂度：O(n)
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022 年 12 月，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录