Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Solution
此题要求时间复杂度低于 \(O(n\log n)\). 所以不能使用 \(sort\).
先用 \(map\) 来存储每个数字出现的次数，然后将其 \(push\) 到优先队列里 \(priority\_queue\)，最后 \(pop\) 出前 \(k\) 个即可
点击查看代码
class Solution {
private:
unordered_map<int,int> mp;
vector<int> ans;
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
for(int i=0;i<nums.size();i++){
mp[nums[i]]++;
}
priority_queue<pair<int,int>> q;
for(auto ele:mp){
q.push({ele.second, ele.first});
}
for(int i=0;i<k;i++){
auto f = q.top();q.pop();
ans.push_back(f.second);
}
return ans;
}
};