题解 | #最小的K个数#

思路：

1. 可以在快排的基础上解决，快排其实就是将某个数放到它在数组中的正确位置上，左边都小于它，右边都大于它，本题中无需使整个数组有序，只要找到排序后位置在k+1的数字即可，此时由左到该数字刚好是最小的k个数字。
2. 用长度为k的大顶堆解决，堆顶存放最大值，若当前数字小于堆顶元素，则替换堆顶元素，由于大顶堆的排序规则，堆中的最大值总会被放到堆顶，所以最后堆中存放的就是最小的k个数。

代码：

import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //长度为k的大顶堆
        ArrayList<Integer> res=new ArrayList<>();
        if(k==0||k>input.length){
            return res;
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer i1,Integer i2){
                return i2.compareTo(i1);
            }
        });
        for(int i=0;i<k;i++){
            queue.offer(input[i]);
        }
        for(int i=k,len=input.length;i<len;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;
//         //快排解决
//         ArrayList<Integer> res=new ArrayList<>();
//         quickSort(input,0,input.length-1,k);
//         for(int i=0;i<k;i++){
//             res.add(input[i]);
//         }
//         return res;
    }
    
    private void quickSort(int[] input,int left,int right,int k){
        if(left<right){
            if(right-left+1<=k){
                return;
            }
            int i=left,j=right;
            int temp=input[i];
            while(i<j){
                while(i<j&&input[j]>=temp){
                    j--;
                }
                if(i<j){
                    input[i]=input[j];
                    i++;
                }
                while(i<j&&input[i]<=temp){
                    i++;
                }
                if(i<j){
                    input[j]=input[i];
                    j--;
                }
            }
            input[i]=temp;
            int kk=k-(i-left+1);
            if(kk==0){
                return;
            }else if(kk>0){
                quickSort(input,i+1,right,kk);
            }else{
                quickSort(input,left,i-1,k);
            }
        }
    }
}