Top K Frequent Elements - Medium - L
Published:
Question
- https://leetcode.com/problems/top-k-frequent-elements/
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Approach
- Maps and queue
Solution
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
priority_queue<pair<int, int>, vector<pair<int,int> >, greater<pair<int,int> > > pq;
map<int,int> m;
int n = nums.size();
for(int i=0;i<n;i++){
if(m.find(nums[i])==m.end()){
m.insert(make_pair(nums[i],1));
} else{
m[nums[i]]++;
}
}
map<int,int>::iterator it;
for(it=m.begin();it!=m.end();it++){
if(pq.size()<k){
pq.push(make_pair(it->second, it->first));
} else{
if(pq.top().first<it->second){
pq.pop();
pq.push(make_pair(it->second, it->first));
}
}
}
stack<int> s;
while(!pq.empty()){
s.push(pq.top().second);
pq.pop();
}
vector<int> ans;
while(!s.empty()){
ans.push_back(s.top());
s.pop();
}
return ans;
}
};