【堆】B000_LC_前 K 个高频元素（快速选择）

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

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

提示：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
你可以按任意顺序返回答案

方法一：快速选择

第一次快速可将1个在基准值x右边但大于x的元素归到x的左边作为答案，k次可保证有k个

typedef pair<int, int> pii;
class Solution {
public:
    vector<int> ans;
    void quick_select(int l, int r, int k, vector<pii>& A) {
        if (l>r) return;
        if (l==r && k==1) {
            ans.emplace_back(A[l].first);
            return;
        }
        int i=l-1, j=r+1, x=A[(l+r)>>1].second;
        while (i<j) {
            do i++; while(A[i].second>x);  //将大于x.second的数都放在左边
            do j--; while(A[j].second<x);
            if (i<j) swap(A[i], A[j]);
        }
        if (j-l+1>=k) { //左边够了k个
            quick_select(l, j, k, A);
        } else {
            for (int p=l; p<=j; p++) ans.emplace_back(A[p].first);
            quick_select(j+1, r, k-(j-l+1), A);
        }
    }
    vector<int> topKFrequent(vector<int>& arr, int k) {
        unordered_map<int, int> mp;
        for (int x : arr) mp[x]++;
        vector<pii> B;
        for (auto p : mp) B.emplace_back(p);
        quick_select(0,B.size()-1,k,B);
        return ans;
    }
};

复杂度分析

• Time：\(O(nlogk)\)，
• Space：\(O(n)\)