我们解决这个问题最简单的方法就是将序列直接进行一次排序，再进行遍历即可获得TopK，但是我们只需要获得TopK的数据，并不需要获得所有元素的序列，这样的方法浪费了很多时间复杂度，因此下面介绍两种更加优秀的方法来解决TopK问题

基于堆排序

流程

  1. 共n个数，先建立一个k个数的小根堆
  2. 初始化i=k+1
  3. 如果i>n则结束否则进行下面操作
    1. 若a[i]>堆顶元素则替换堆顶，shiftdown操作让堆顶元素到达正确位置，若a[i]<=堆顶元素则直接进行第二步
    2. i++
  4. 结束后堆顶就是第k大的数字，堆里就是倒序的前k大的数

时间复杂度分析

  1. 建k个数的堆：O(k)
  2. 后面数据进行比较调整
    1. 最坏情况：k+1开始每个数都比堆顶大，遍历原数组中剩余元素需要O(n-k)的时间复杂度，每个剩余的元素进行shiftdown操作，k个元素有Logk层则每个数调整Logk次时间复杂度为O(Logk)
    2. 最好情况：后面的都不需要调整了，前k个数正好是堆Topk大的数，因此只需要遍历原数组中剩余元素，复杂度为O(n-k)
  3. 总体时间复杂度：
    1. 最坏：O(n+(n-k)*Logk)
    2. 最好：O(n)
  4. 空间复杂度：空间复杂度：O(logn)，递归使用栈空间的空间代价的期望为 O(logn)。

代码

void TestTopK(int* a, int n, int k)
{
    //建堆,最后一个非叶子结点的下标是(k-1-1)/2。
    for(int i=(k-1-1)/2; i>=0; i--)
    {
        ShiftDown(a, k, i);
    }
    //调整
    for(int i=k+1; i<n; i++)
    {
        if(a[i] > a[0])
        {
            Swap(&a[0], &a[i]);
            ShiftDown(a, k, 0);
        }
    }
}

代码出处

基于快速排序

流程

  1. 基于快速排序，寻找TopK元素，实际上我们找的就是nums[k-1]的数
  2. 进行一次快排的partition（划分），若pivot所在的index>k-1则说明nums[index]>nums[k-1]则需要在pivot左边继续进行一次partition，若<k-1则在右边找，若index=k-1说明找到了
  3. 重复第二步直到index=k-1，nums[k-1]就是第TopK大的数

复杂度分析

  1. 时间复杂度：O(n)
  2. 空间复杂度：O(logn)，递归使用栈空间的空间代价的期望为 O(logn)。

代码

class Solution {
public:
    int quickSelect(vector<int>& a, int l, int r, int index) {
        int q = randomPartition(a, l, r);
        if (q == index) {
            return a[q];
        } else {
            return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
        }
    }
​
    inline int randomPartition(vector<int>& a, int l, int r) {
        int i = rand() % (r - l + 1) + l;
        swap(a[i], a[r]);
        return partition(a, l, r);
    }
​
    inline int partition(vector<int>& a, int l, int r) {
        int x = a[r], i = l - 1;
        for (int j = l; j < r; ++j) {
            if (a[j] <= x) {
                swap(a[++i], a[j]);
            }
        }
        swap(a[i + 1], a[r]);
        return i + 1;
    }
​
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(0));
        return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
    }
};

代码出处

赏