快排思想

• 注意，这里是倒序排序，因此应该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;
    }
};