【347. 前K个高频元素】哈希表重新定义cmp / 哈希表+桶排序

 方法一：直接使用哈希表，通过重新定义sort函数的cmp方式，注意sort函数只能对pair为元素的vector数组排序，不能直接对map排序！

class Solution {
public:
    static bool cmp(pair<int, int>& m, pair<int, int>& n) {
        return m.second > n.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        // 1.统计元素出现频率
        for(int i = 0 ; i < nums.size() ; i ++) {
            map[nums[i]] ++;
        }

        // 2.由于sort不能对map直接进行排序，故转化为pair进行排序，单调递减
        vector<pair<int, int>> map1(map.begin(),map.end());
        sort(map1.begin(),map1.end(),cmp);//用sort排序

        // 3.前k个最大的拿出来即可
        vector<int> res;
        auto iter = map1.begin();
        while(k --) {
            res.push_back(iter->first);
            iter ++;
        }
        return res;
    }
};

方法二：哈希表+桶排序，划分成 (n+1) 个桶（0-n），n为nums.size( )，即最极端的情况，所以元素都相同，那么数量为n。然后从桶中倒序输出K个。

//哈希表计数+桶排序
class Solution {
public:
    unordered_map<int,int> hashmap;
    vector<int> topKFrequent(vector<int>& nums, int k) {
        for(auto &i:nums)
        {
            hashmap[i]++;
        }
        vector<vector<int>> bucket(nums.size()+1);//0-n
        for(auto &i:hashmap)
        {
            bucket[i.second].push_back(i.first);
        }
        vector<int>ans;
        int j=0;
        for(int i=bucket.size()-1;i>=0&&j<k;i--)
        {
            for(auto &x:bucket[i])
            {
                j++;
                ans.push_back(x);
            }
        }
        return ans;
    }
};