Top K总结：寻找第k大元素

TopK，得到答案并不难，但不断优化的过程，挺艰难。

题目描述:
有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。 

1.全局排序，时间复杂度取决于排序算法，一般是 O(n*lgn)。 相信大多数朋友看到这题的思路就是排序，返回第k大的值，甚至还有小机灵鬼直接调用内置方法

public int findKth(int[] a, int n, int K) {
    Arrays.sort(a);
    return a[n-K];
}

2.局部排序，只排序TopK个数，O(n*k)，冒泡、直接选择、直接插入都可以，但k的取值趋近n时，时间复杂度又趋近与O(n^2)。

public int findKth(int[] a, int n, int K){
    // 冒泡k次
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
               int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr[n - K];
}

3.堆，TopK个数也不排序了，O(n*lg(k)),想练手的可以模仿堆排序手动维护小根堆。也可以使用最小优先队列。

public int findKth(int[] a, int n, int K){
    // 暂存 第k大的值
    PriorityQueue<integer> queue = new PriorityQueue<>(K);
    // n * 调整 lgk
    for (int num : a) {
        if (queue.isEmpty() || num > queue.peek()) {
            if (queue.size() >= K) {
                queue.poll();
            }
            queue.add(num);
        }
    }
    return queue.isEmpty() ? 0 : queue.peek();
}

上面的代码有bug，纠正代码 ↓↓↓

    public int findKth(int[] a, int n, int K){
        // 暂存K个较大的值，优先队列默认是自然排序（升序），队头元素（根）是堆内的最小元素，也就是小根堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(K);
        // 遍历每一个元素，调整小根堆
        for (int num : a) {
            // 对于小根堆来说，只要没满就可以加入（不需要比较）；如果满了，才判断是否需要替换第一个元素
            if (queue.size() < K) {
                queue.add(num);
            } else {
                // 在小根堆内，存储着K个较大的元素，根是这K个中最小的，如果出现比根还要大的元素，说明可以替换根
                if (num > queue.peek()) {
                    queue.poll(); // 高个中挑矮个，矮个淘汰
                    queue.add(num);
                }
            }
        }
        return queue.isEmpty() ? 0 : queue.peek();
    }

4.快速排序的思想--随机选择法，时间复杂度 O(n) 需要理解两个思想，快排的分治，二分查找的剪枝 分治法，每个分支“都要”递归，例如：快速排序，O(n*lg(n)) 减治法，“只要”递归一个分支，例如：二分查找O(lg(n))，随机选择O(n) TopK的另一个解法：随机选择 + partition

以下是网上找到的一些伪代码在partition是从大到小排序，不符合个人的习惯。导致后续的伪代码都很难弄懂。

int RS(arr, low, high, k){
    if(low == high) return arr[low];
    i = partition(arr, low, high);
    temp = i - low; //数组前半部分元素个数
    if (temp >= k)
        return RS(arr, low, i-1, k); //求前半部分第k大
    else
        return RS(arr, i+1, high, k-i); //求后半部分第k-i大
}

于是自己摸索了好久，写出了以下代码，partition+二分法，其实要找第k大，前面的排序再取值已经知道了第K大的数，下标是len - k。那么partition能直接定位到len - k 的位置就找到了结果。如何找呢，就用到了二分查找的思想，不断接近len-k的位置，最终返回结果。

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        return quickSort(a, 0, a.length - 1, K);
    }

    private int quickSort(int[] arr, int left, int right, int k){
        int p = partition(arr, left, right);
        // 改进后，很特殊的是，p是全局下标，只要p对上topK坐标就可以返回
        if (p == arr.length - k) {
            return arr[p];
        }else if (p < arr.length - k) {
            // 如果基准在左边，这在右边找
            return quickSort(arr, p + 1, right,k);
        }else {
            return quickSort(arr, left, p - 1,k);
        }
    }

    private int partition(int[] arr, int left, int right) {
        // 可优化成随机，或中位数
        int key = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= key) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= key) left++;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
}

如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。 祝大家牛年大吉！AC 多多，Offer 多多！加油！