题解| #最小的K个数#

题目描述

给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组
示例1
输入：[4,5,1,6,2,7,3,8],4
返回值：[1,2,3,4]

题目分析

这类题目又称TopK问题，在面试中较为常见，表述为给定一个数组，找出其中最大或最小的k个数，直观的做法是，将整个数组排好序后，取数组前k个或最后k个数，但这种方法时间复杂度较高(O(n*log(n)))，在数据量很大的情况不适用。

解题思路

方法1：堆排序，可以维持一个大小为k的大顶堆，若是后面有比大顶堆堆顶数据小的数，则可以放入，且将原来的堆顶数据拿出，堆排序只要维持堆的顺序，减少了所需时间。
向堆中放入k个数据

遍历k后面的数据，当小于堆顶数据时，

遍历k后面的数据，当大于堆顶数据时，

方法2：快速排序思想，快速排序的基本思想是每次确定一个哨兵数据，根据这个哨兵数据，将数组中所有比它小的放到它的左边，比它大的放到它的右边，起到一个分区的作用。

实现主要思路：
1.首先可以随机取一个数作为哨兵，它将数组分区后，判断它所处的下标index是否等于k；
2.若等于k，则此时前k个数就是0~k-1，但是这k个数是无序的，只能保证它们是最小的k个数（在右边的都比它们大）；
3.若小于k，则要往右边部分再找k-index个数；
4.若大于k，则要往左边部分减少范围确认k的位置；

代码实现

方法1：堆排序，在java中，优先级队列PriorityQueue实现了堆排序，可以借助它来存储目标的k个数。

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        // 处理不合理的情况
        if (k == 0 || k > input.length) { 
            return res;
        }
        // 构建大顶堆，默认小顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            public int compare(Integer num1, Integer num2) {
                return num2 - num1;
            }
        });
        // 将数组中前k个数放入堆中
        for (int i = 0; i < k; ++i) {
            queue.offer(input[i]);
        }
        //对后面的数进行比较，判断是否放入堆中
        for (int i = k; i < input.length; ++i) {
            // input[i]要小于堆顶数据，放入
            if (queue.peek() > input[i]) {
                queue.poll();
                queue.offer(input[i]);
            }
        }
        for (int i = 0; i < k; ++i) {
            // 将堆中数据放入结果中
            res.add(queue.poll());
        }
        return res;
    }

时间复杂度：O(nlogk)，需要遍历数组，同时要维护长度为k的堆的顺序，因为堆的特性，维护消耗logk，所以总时间复杂度为O(nlogk)。
空间复杂度：O(k)，维护的大顶堆最多存储k个数。

方法2：快速排序思想，与一般的快速排序相比，只用操作数组的一半（大于或小于情况中的一种，有判断），原来的快速排序需要对这两种情况都进行处理（无判断）。

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        // 处理不合理的情况
        if (k == 0 || k > input.length) {
            return res;
        }
        // 快速排序及分区
        quickSort(input, k, 0, input.length - 1);
        // 获取数组的前k个数
        for (int i = 0; i < k; ++i) {
            res.add(input[i]);
        }
        return res;
    }
    private void quickSort(int[] arr, int k, int l, int r) {
        if(l == r || l >= arr.length) return;
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        // 若i大于k，则要往前找
        if (i > k) quickSort(arr, k, l, i - 1);
        // 若i小于k，则要往后找
        if (i < k) quickSort(arr, k, i + 1, r);
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

时间复杂度：O(n)，对于长度为 n 的数组执行哨兵划分操作的时间复杂度为 O(n) ；每轮哨兵划分后根据 k 和 i 的大小关系选择递归，由于 i 分布的随机性，则向下递归子数组的平均长度为 n/2 ；因此平均情况下，哨兵划分操作一共有 n + n/2 + n/4 + ... + n/n = n + (n-1)/n < 2n ，总体时间复杂度为 O(n)。
空间复杂度：O(logn)，划分函数的平均递归深度为O(logn)。