剑指offer40.最小的k个数

• 前言
• 一、选择排序
• 二、堆排

最小的k个数考察的是排序的基础，在已给K为多少的情况下，可以用选择排序。考虑堆排序的速度，也可以使用堆排，Java里使用优先队列。

//剑指offer40.最小的k个数
    public int[] getLeastNumbers(int[] arr, int k) {
        //可以使用选择排序，选择前k个
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length;j++){
                if(arr[min] > arr[j]){
                    min = j;
                }
            }
            res[i] = arr[min];
            arr[min] = arr[i];
        }
        return res;
    }

//堆排解决top-K
    public int[] getLeastNumbers(int[] arr, int k) {
        if(k==0||arr.length == 0)
            return new int[0];
        int[] res = new int[k];
        //将默认的大根堆改为小根堆
        Queue queue = new PriorityQueue<>(((o1, o2) -> o2.compareTo(o1)));
        for(int num : arr){
            if(queue.size() < k){
                queue.offer(num);
            }
            else if(num < queue.peek()){
                queue.poll();
                queue.offer(num);
            }
        }
        int index = 0;
        for(int num : queue){
            res[index++] = num;
        }
        return res;
    }