问题

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

算法：计数排序

这道题的暴力解法很容易想到：先统计每个元素的频次，再按照频次排序，取TopK即可。

如果直接用内置的快速排序函数，时间复杂度为$O(NlogN)$。由于题目要求复杂度必须优于$O(NlogN)$, 我们考虑下怎么优化。

实际上，对频次排序除了考虑用快速排序，还可以用更快的计数排序$O(N)$。这是因为频次是有范围的整数（0~nums.size())，符合计数排序的条件

因此，我们需要处理出频次的计数数组，从大到小依次枚举，找到前k高频次分界点，再枚举输出即可

时间复杂度

$O(N)$

代码

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for(int x: nums){
            cnt[x] ++;
        }

        int n = nums.size();
        vector<int> s(n+1); // s[i]: 频次为i的计数值
        for(auto [x, c]: cnt){
            s[c] ++;
        }

        int t = 0, i = n;
        while(t < k) t += s[i--]; // 找到前k高频次分界点：频次大于i即为频次topK的元素
        vector<int> res;
        for(auto [x, c]: cnt){
            if(c > i){
                res.push_back(x);
            }
        }

        return res;

    }
};