什么是TopK问题？

简单来说是在一堆数据里面找到前K大的数

这一类问题无论是面试还是实际开发中都是非常经典的问题

立刻就能想到的解法——排序

既然要前K大的数，那么最直接的当然就是排序了，通过如快排等效率较高的排序算法，可以在平均时间为O(nlogn)的时间复杂度内找到结果。

通过二叉搜索树TreeMap
也可以做到O(nlogn)的时间复杂度

这种方式在这种场景固然还有优化的余地

O(n)时间复杂度的排序！

熟悉了快排的应该都知道，快排是可以是用来查找某些位置的数值的问题，例如计算中位数

快排先找数在排序，保证一组的数的基准一定在正确的位置上。

当然也适用于TopK问题(毕竟快排的优化之一就是对于一定范围内的数使用插入排序，判断范围在快排内部是相当简单的)。

具体过程如下：每次经过划分，如果中间值等于K，那么左边的数就是TopK的数据；当然，如果不等于，只要递归处理左边或者右边的数就可以了。

代码实现：

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 最后一个参数表示我们要找的是下标为k-1的数
        return quickSearch(arr, 0, arr.length - 1, k - 1);
    }

    private int[] quickSearch(int[] nums, int lo, int hi, int k) {
        // 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
        int j = partition(nums, lo, hi);
        if (j == k) {
            return Arrays.copyOf(nums, j + 1);
        }
        // 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
        return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
    }

    // 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
    private int partition(int[] nums, int lo, int hi) {
        int v = nums[lo];
        int lt = lo, gt = hi+1;
        while (true) {
            while (++lt <= hi && nums[lt] < v);
            while (--gt >= lo && nums[gt] > v);
            if (lt >= gt) break;
            swap(nums, gt, lt);
        }
        nums[lo] = nums[gt];
        nums[gt] = v;
        return gt;
    }

    void swap(int[] nums, int x, int y) {
        if (x == y) return;
        nums[x] ^= nums[y];
        nums[y] ^= nums[x];
        nums[x] ^= nums[y];
    }
}

该方法的时间复杂度是O(n)，第一次划分数组是n，后面每次遍历平均缩短一半。

这种方法的缺点依旧相当明显，最主要就是内存问题，在海量的数据之下，我们很可能无法一次性将数据全部加载入内存。

利用分布式思想处理海量数据

面对海量数据容易往分布式方向思考

我们可以将数据分散在多台机器中，然后每台机器并行计算各自的TopK数据，最后汇总得到最终的TopK数据。

最经典的方法——堆

维护一个大小为K的小顶堆，依次将数据放入堆中，当堆的大小满了的时候，就将堆顶元素与下一个元素比较，如果大于堆顶元素就将堆顶抛弃，并将元素插入堆中。

代码如下

// 保持堆的大小为K，然后遍历数组中的数字，遍历的时候做如下判断：
// 1. 若目前堆的大小小于K，将当前数字放入堆中。
// 2. 否则判断当前数字与大根堆堆顶元素的大小关系，如果当前数字比大根堆堆顶还大，这个数就直接跳过；
//    反之如果当前数字比大根堆堆顶小，先poll掉堆顶，再将该数字放入堆中。
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr.length == 0) {
            return new int[0];
        }
        // 默认是小根堆，实现大根堆需要重写一下比较器。
        Queue<Integer> pq = new PriorityQueue<>((v1, v2) -> v2 - v1);
        for (int num: arr) {
            if (pq.size() < k) {
                pq.offer(num);
            } else if (num < pq.peek()) {
                pq.poll();
                pq.offer(num);
            }
        }
        
        // 返回堆中的元素
        int[] res = new int[pq.size()];
        int idx = 0;
        for(int num: pq) {
            res[idx++] = num;
        }
        return res;
    }
}
/**
作者：sweetiee
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/3chong-jie-fa-miao-sha-topkkuai-pai-dui-er-cha-sou/  **/