随机数组中前k小的数，按顺序输出。

坑点：k会大于数组长度，这个时候要输出空的ArrayList。

第一感觉就是先排序然后取前k个就完了。。。。时间复杂度就是快排的时间复杂度。
但是这样有个问题，数组太长排序会比较非内存。
合理的解法：取数组的前k个维护一个集合A，然后遍历后续的其他数，如果其他数中有比A中最大值还要大的数字，那就把这个数字替换掉A的最大值。最后得到的集合A中就存的是最小的k个数了。排个序就好了。
如果说每次去找A中的最大值比较费时，可以降序的优先队列，在输出结果的时候poll也是有序的。

普通解法

import java.util.Arrays;
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> arr = new ArrayList<>();
        if(k>input.length){
            return arr;
        }
        Arrays.sort(input);
        for(int i=0;i<k;i++){
            arr.add(input[i]);
        }
        return arr;
    }
}

更好的解法

import java.util.*;

public class Solution {

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

        PriorityQueue <Integer> pQueue = new PriorityQueue<>(k, Comparator.reverseOrder());
        for(int i=0;i<k;i++){
            pQueue.add(input[i]);
        }
        for(int i=k;i<input.length;i++){
            if(input[i]<pQueue.peek()){
                pQueue.poll();
                pQueue.add(input[i]);
            }
        }
        LinkedList<Integer> list = new LinkedList<>();
        for(int i=0;i<k;i++){
            list.addLast(pQueue.poll());
        }
        arr.addAll(list);

        return arr;

    }
}