中等
给你一个整数数组 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)