介绍

Top K 问题是求数组中前k个最大数的问题，或者求数组中出现频率最高的k个数，后者只需要用哈希表记录每个数的出现频率，问题就转化成求出现次数数组中前k个最大数。

算法

1.局部排序，时间复杂度$O(n * k)$

局部冒泡排序，由于冒泡排序每次可以求出一个最大或最小的元素，所以我们不需要求出所有元素的顺序，只需要进行k趟冒泡，求出前k个最大的元素即可。输出的k个最大数是有序的。

局部选择排序，由于选择排序每次从待选择的序列里选出一个最大或最小的元素，所有当选出前k个元素后就可以退出。输出的k个最大数是有序的。

2.堆排序，时间复杂度$O(klogn)$

首先对n个元素的数组建堆（线性时间复杂度），对于建好的大根堆，每次输出最大的元素，并调整。输出的k个最大数是有序的。

或先把前k个元素建成大小为k的小根堆，依次将后面的元素与最小的元素对比，若更大则替代最小的元素并调整堆，若更小则比较下一个，一直比较完，堆中的元素就是前k个最大的。输出的k个最大数是有序的。

3.快速选择，平均时间复杂度$O(n)$

快速选择每次选择一个pivot，并使用双指针将大于等于pivot的数放在左边区间，小于等于pivot的数放在右边区间，如果左边区间的长度大于k，则再对左边区间使用快速选择，如果小于等于k，则将左边区间的值记录到答案数组中，对右边区间进行快速选择(k – 左边区间长度)。输出的k个最大数是无序的。

快速选择用来求数组中TopK的k个数，或数组中第k大的数（中位数等）

例：力扣面试题17.14最小的k个数：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
void qSelect(int *arr, int l, int r, int k, int *ans, int *idx){
    if(l >= r)return;
    int pivot = arr[l], i = l - 1, j = r + 1;
    while(i < j){
        do i++; while(arr[i] < pivot);
        do j--; while(arr[j] > pivot);
        if(i < j)swap(&arr[i], &arr[j]);
    }
    if(j - l + 1 <= k){
        for(int i = l; i <= j; i++){
            ans[*idx] = arr[i];
            (*idx)++;
        }
        qSelect(arr, j + 1, r, k - j + l - 1, ans, idx);
    } else {
        qSelect(arr, l, j, k, ans, idx);
    }
}
int* smallestK(int* arr, int arrSize, int k, int* returnSize) {
    int *ans = (int *)malloc(sizeof(int) * k), idx = 0;
    *returnSize = k;
    qSelect(arr, 0, arrSize - 1, k, ans, &idx);
    return ans;
}

4.BFPRT算法，时间复杂度$O(n)$

拓展

如果要求实时更新并输出最大的k个数，如有一个战力排行榜，需要实时显示前K名的玩家。