题解 | #最小的K个数#

堆排序

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res=new ArrayList<>();
        for(int i=input.length/2-1;i>=0;i--){
            maxheap(input,i,input.length);
        }
        for(int i=input.length-1;i>=input.length-1-(k-1);i--){
            swap(input,i,0);
            maxheap(input,0,i);
        }
        for(int i=input.length-1;i>=input.length-k;i--){
            res.add(input[i]);
        }
        return res;
    }
    void swap(int[] a,int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
    void maxheap(int[] a,int i,int length){
        int temp=a[i];
        for(int k=2*i+1;k<length;k=2*k+1){
            if(k+1<length&&a[k+1]<a[k]){
                k=k+1;
            }
            if(a[k]<temp){
                a[i]=a[k];
                i=k;
            }
            else break;
        }
        a[i]=temp;
    }
}