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

示例 1：

**输入：**nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

**输入：**nums = [1], k = 1

输出：[1]

示例 3：

**输入：**nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

提示：

1 <= nums.length <= 10(5)

-10(4) <= nums[i] <= 10(4)

k 的取值范围是 [1, 数组中不相同的元素的个数]

题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

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

统计出出现频次后与找topK类似，可使用小顶堆或快速排序的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    vector<int> topKFrequent(vector<int> &nums, int k) {
        unordered_map<int, int> flag;
        for (int i = 0; i < nums.size(); i++) {
            flag[nums[i]]++;
        }
        vector<pair<int, int>> fre;
        for (auto i : flag) {
            fre.push_back({i.first, i.second});
        }
        int n = fre.size();
        quickSelect(fre, 0, n - 1, n - k);
        vector<int> ans;
        for (int i = 0; i < k; i++) {
            ans.push_back(fre[n - 1 - i].first);
        }
        return ans;
    }
    void quickSelect(vector<pair<int, int>> &nums, int l, int r, int k) {
        if (l >= r)
            return;
        int i = l;
        int j = r;
        int p = nums[l].second;
        while (i < j) {
            while (i < j && nums[j].second >= p)
                j--;
            while (i < j && nums[i].second <= p)
                i++;
            swap(nums[i], nums[j]);
        }
        swap(nums[i], nums[l]);
        if (i == k) {
            return;
        } else if (i > k) {
            quickSelect(nums, l, i - 1, k);
        } else {
            quickSelect(nums, i + 1, r, k);
        }
    }
};