一、题目内容

二、题解

解法1：

思路

使用大顶堆，堆顶保存最小数集合的最大值；构建堆完成后依次入堆，判断当前元素小于堆顶则置换，之后重新调整堆，使堆内数据均小于堆顶。

代码

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(input == null || k == 0){
            return result; 
        }
        int[] maxHeapArr = new int[k];
        int i;
        for(i=0;i<k;i++){
            maxHeapArr[i] = input[i];
        }
        buildMaxHeap(maxHeapArr);
        for(;i<input.length;i++){
            if(input[i]<maxHeapArr[0]){
                maxHeapArr[0] = input[i];
                adjustMaxHeap(maxHeapArr,0);
            }
        }
        for(int num:maxHeapArr){
            result.add(num);
        }
        return result;
    }
    public void buildMaxHeap(int[] maxHeapArr){
        for(int k = maxHeapArr.length/2-1;k>=0;k--){
            adjustMaxHeap(maxHeapArr,k);
        }
    }
    public void adjustMaxHeap(int[] maxHeapArr,int adjustPos){
        int len = maxHeapArr.length;
        int temp = maxHeapArr[adjustPos];
        for(int k = adjustPos*2+1;k<len;k=k*2+1){
            if(k+1<len&&maxHeapArr[k]<maxHeapArr[k+1]){
                k++;
            }
            if(maxHeapArr[k]>temp){
                maxHeapArr[adjustPos] = maxHeapArr[k];
                adjustPos = k;
            }else{
                break;
            }
        }
        maxHeapArr[adjustPos] = temp;
    }
}