快排思想
- 注意，这里是倒序排序，因此应该
while(nums[i].cnt>x);
class Solution {
public:
struct element
{
int val,cnt;
element(int a,int b)
{
val=a;
cnt=b;
}
};
vector<int> res;
void quick(vector<element>& nums, int l,int r,int k)
{
if(l==r)
{
res.push_back(nums[l].val);
return;
}
int x=nums[(l+r+1)>>1].cnt;
int i=l-1,j=r+1;
while(i<j)
{
do i++;while(nums[i].cnt>x);
do j--;while(nums[j].cnt<x);
if(i<j) swap(nums[i],nums[j]);
}
cout<<i<<' '<<j<<' '<<k<<endl;
if(i-l==k)
{
for(int k=l;k<i;k++)
res.push_back(nums[k].val);
return;
}
else if(i-l>k)
quick(nums,l,i-1,k);
else
{
for(int k=l;k<i;k++)
res.push_back(nums[k].val);
quick(nums,i,r,k-i+l);
}
}
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> mp;
for(auto x:nums) mp[x]++;
vector<element> q;
for(auto x:mp) q.push_back({x.first,x.second});
quick(q,0,q.size()-1,k);
return res;
}
};
堆
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> mp;
for(auto x:nums) mp[x]++;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
for(auto item:mp)//维护大小为k的小根堆
{
if(q.size()<k) q.push(make_pair(item.second,item.first));
else if(item.second>q.top().first)
{
q.pop();
q.push(make_pair(item.second,item.first));
}
}
vector<int> res;
for(int i=0;i<k;i++)
{
res.push_back(q.top().second);
q.pop();
}
return res;
}
};
我的解法
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> hashmap;
multimap<int,int> mp;
vector<int> res;
for(auto x:nums) hashmap[x]++;
for(auto item:hashmap)
mp.insert(make_pair(item.second,item.first));
for(auto i=mp.rbegin();i!=mp.rend()&&k;k--,i++)
res.push_back(i->second);
return res;
}
};