# [C++] Two clean O(nlogk) solutions (map/MinHeap)

• Solution 1. Maintain a map<frequency, number(s)> of `k` elements with 'largest' frequency, each `insert` and `erase` operation takes `O(logk)` time.

``````    vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int>res;
map<int,vector<int>>mp; //use vector here cuz some numbers may have same frequency.
unordered_map<int,int>hmap;
for(auto x:nums) hmap[x]++;
int count=0;
for(auto x:hmap){
if(count<k) mp[x.second].push_back(x.first),count++;
else{
mp[x.second].push_back(x.first),count++;
count-=mp.begin()->second.size();
mp.erase(mp.begin());
}
}
for(auto x:mp)
for(auto y:x.second)
res.push_back(y);
return res;
}
``````

Solution 2. Simply replace the map with a priority_queue(MinHeap),
top(): `O(1)`
pop(): `O(2*log(k))`
push() : `O(log(k))`

``````class Solution {
private:
struct compare
{
bool operator ()(pair<int,int>&p1,pair<int,int>&p2){ return p1.first > p2.first; }
};
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
vector<int> res;
unordered_map<int,int>m;
priority_queue<pair<int,int>,vector<pair<int,int>>,compare> pq;
for(auto x:nums) m[x]++;
for(auto x:m){
pq.push(make_pair(x.second, x.first));
if(pq.size()>k) pq.pop();
}
while(!pq.empty()) res.push_back(pq.top().second), pq.pop();
return res;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.