//347. Top K Frequent Elements
Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
#include <iostream>
#include <unordered_map>
#include <vector>
#include <cassert>
#include <queue>
using namespace std;
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
//element,frequency hash/iter
unordered_map<int,int> hash;
unordered_map<int,int>::iterator iter;
for(int i=0;i<nums.size();i++){
hash[nums[i]]+=1;
}
assert(k<=hash.size());
//freqency,element q
priority_queue< pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > q;
for(iter=hash.begin();iter!=hash.end();iter++){
if(q.size()==k){
if(iter->second>q.top().first){
q.pop();
q.push(make_pair(iter->second,iter->first));
}
} else{
q.push(make_pair(iter->second,iter->first));
}
}
vector<int> res;
while(! q.empty()){
res.push_back(q.top().second);
q.pop();
}
return res;
}
};
int main(){
int arr[]={1,1,1,2,2,3};
vector<int> vec(arr,arr+sizeof(arr)/sizeof(int));
int k=2;
vector<int> res=Solution().topKFrequent(vec,k);
for(int i=0;i<res.size();i++){
cout<<res[i]<<" ";
}
cout<<endl;
return 0;
}
