牛客-NC119-最小的K个数

方法一：PriorityQueue（优先队列）

思路：这里先简单介绍PrioriryQueue，它是Queue接口的一个队列实现类，即优先队列，但它的排序不是典型的我们熟知的队列式的FIFO（先进先出）方式。具体来说，分为两种排序：一种是自然排序，即实现Comparable接口的compareTo方法，默认是按照加入元素的大小从小到大排序。另一种是定制排序，就是new对象后面的Comparator对象，重写Compare(Object o1, Object o2)方法来实现定制排序的。说了这么多，一言以蔽之，这里我们是可以直接使用PrioriryQueue来解决这个问题，为什么？因为PrioriryQueue的排序是堆排序，而堆排序可以保证第一个元素也就是大顶堆或小顶堆的根节点是当前优先队列里最大或最小的元素，同时，当使用offer()或poll()之后，这个堆都会再次堆化（也就是重新进行堆排），所以我们可以写出如下代码：

import java.util.*;

public class Solution {
   
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
   
        // 特判
        ArrayList<Integer> ret = new ArrayList<>();
        int len = input.length;
        if (len == 0 || k > len) {
   
            return ret;
        }

        PriorityQueue<Integer> pq = new PriorityQueue();
        for (int i = 0; i < len; i++) {
   
            pq.offer(input[i]);
        }
        for (int i = 0; i < k; i++) {
   
            ret.add(pq.poll());
        }
        return ret;
    }
}

时间复杂度： O(NlogN)，这是小根堆的时间复杂度。
空间复杂度： O(N), 我们使用大小为N的PriorityQueue来存数据。
注：这里使用大根堆求解可以进一步优化时间和空间复杂度！

方法二：基于快排的数组划分

思路：可以看LeetCode题解，方法二： 基于快速排序的数组划分。

import java.util.ArrayList;

public class Solution {
   
    // 交换
    private static void swap(int[] arr, int i, int j) {
   
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    // 类快排
    private  static ArrayList<Integer> quickSort(int[] arr, int k, int l, int r) {
   
        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);
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);

        ArrayList<Integer> ret = new ArrayList<>();
        for (int m = 0; m < k; m++) {
   
            ret.add(arr[m]);
        }
        return ret;
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
   
        // 特判
        ArrayList<Integer> ret = new ArrayList<>();
        int len = input.length;
        if (k > len) return ret;
        if (len == 0 || k == len) {
   
            for (int i = 0; i < len; i++) {
   
                ret.add(input[i]);
            }
            return ret;
        }

        return quickSort(input, k, 0, input.length - 1);
    }
}

时间复杂度： O(N), 其中N为数组元素数量；对于长度为N的数组执行哨兵划分操作的时间复杂度为O(N)；而每次向下递归子数组的平均长度为N/2，因此平均情况下，哨兵划分操作一共有N + N/2 + N/4 + … + N/N < 2N，即总体时间复杂度为O(N)。
空间复杂度： O(logN), 划分函数的平均递归深度为O(logN)。