rishavsahayiit
BAN USERclass Solution {
public:
struct mycomp
{
bool operator()(pair<int,int> a,pair<int,int> b)
{
if(a.second<=b.second)
return true;
return false;
}
};
vector<int> topKFrequent(vector<int>& arr, int k) {
unordered_map<int,int> m1;
// map<int,int> m2;
priority_queue<pair<int,int>,vector<pair<int,int>>,mycomp> q;
int n=arr.size();
vector<int> res;
if(n==0)
return res;
for(int i=0;i<n;i++)
{
m1[arr[i]]++;
}
unordered_map<int,int> ::iterator it;
for(it=m1.begin();it!=m1.end();it++)
{
q.push(make_pair(it->first,it->second));
}
int i=0;
//vector<int> res;
while(!q.empty()&&i<k)
{
res.push_back(q.top().first);
q.pop();
i++;
}
return res;
}
};
This is like finding maximum square of all 1's in a boolean matrix.Standard dp question!!
- rishavsahayiit July 03, 2016