计数排序

借助计数排序的思想

1.先统计每个元素出现次数

2.用s数组,s[i]表示出现了i次的元素有s[i]个

3.根据k在s数组中找到一个分界线i，使得前k个高频元素的出现次数都>i次

$ 时间复杂度O(N)，空间复杂度O(N) $

参考文献

lc究极班

AC代码

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int n = nums.size();
        //统计次数
        unordered_map<int,int> m;
        for (auto x : nums) m[x] ++;
        //s[i]表示出现i次的元素个数
        vector<int> s(n + 1, 0);
        for (auto item : m){
            s[item.second] ++;
        }
        //找到分界线i
        int cnt = 0, i = n;
        while (cnt < k) cnt += s[i --];
        //计算答案
        vector<int> res;
        for (auto item : m){
            if (item.second > i)
                res.push_back(item.first);
        }
        return res;
    }
};