方法一：大顶堆

时间复杂度：O(nlongk), 插入容量为k的大根堆时间复杂度为O(longk), 一共遍历n个元素
空间复杂度：O(k)

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (input == null || input.length < k || k <= 0) return res;

        //降序，最大的数在堆顶（这里牛客网要莫名报错，但可以运行）
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((Integer a, Integer b) -> b - a);
        /*PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b) {
                return b - a;
            }
        });*/

        for (int val : input) {
            if (pq.size() < k) pq.offer(val);
            else if (pq.peek() > val) {
                pq.poll();        //！！！注意这里要用 poll()
                pq.offer(val);
            }
        }
        while (!pq.isEmpty()) res.add(pq.poll());
        return res;
    }
}

方法二：快排（推荐）

时间复杂度：O(n)
空间复杂度：O(1)

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (input == null || k <= 0 || input.length < k) return res;
        quickSort(input, 0, input.length - 1);
        for (int i = 0; i < k; i++) {
            res.add(input[i]);
        }
        return res;
    }

    public void quickSort(int[] input, int left, int right) {
        if (left > right) return;
        int i = left;
        int j = right;
        int tmp = input[left];
        while (i < j) {
            while (i < j && input[j] >= tmp) j--;
            while (i < j && input[i] <= tmp) i++;
            if (i < j) {
                int t = input[i];
                input[i] = input[j];
                input[j] = t;
            }
        }
        input[left] = input[i];
        input[i] = tmp;
        quickSort(input, left, i - 1);
        quickSort(input, i + 1, right);
    }
}