Question

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

思路

使用堆排序的方法对数组进行排序后，取前k个最小值，这里手动实现建堆；
升序--使用大顶堆
降序--使用小顶堆

Code

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(input == null || input.length == 0 || k > input.length || k == 0)
            return res;
        //建立大顶堆
        for(int i = input.length; i > 0; i--)
        {
            BuildMaxHeap(input , i);
            Swap(input, i);    //将大值放到后面
        }
        for(int i = 0; i < k; i++)
        {
            res.add(input[i]);
        }
        return res;
    }
    //建立大顶堆
    private void BuildMaxHeap(int[] input , int len)
    {
        //从最后一个非叶子结点开始建立大顶堆
        for(int i = len / 2 - 1; i >= 0; i--)
        {
            //根结点小于左子树
            if((2 * i + 1) < len && input[i] < input[2 * i + 1])
            {
                int tmp = input[i];
                input[i] = input[2*i+1];
                input[2*i+1] = tmp;
                //检查交换后左子树是否满足大顶堆性质
                if(2*(2*i+1)+1< len && input[2*i+1] < input[2*i+1] ||
                   2*(2*i+1) + 2 < len && input[2*i+1] < input[2*(2*i+1)+2])
                {
                    BuildMaxHeap(input, len);
                }
            }
            //根结点小于右子树
            if((2*i+2) < len && input[i] < input[2*i+2])
            {
                int tmp = input[i];
                input[i] = input[2*i+2];
                input[2*i+2] = tmp;
                if(2*(2*i+2) + 1 < len && input[2*i+2] < input[2*(2*i+2)+1] ||
                   2*(2*i+2) + 2 < len && input[2*i+2] < input[2*(2*i+2)+2])
                {
                    BuildMaxHeap(input,len);
                }
            }
        }
    }
    //将根结点与最后一个元素交换位置
    private void Swap(int[] input, int len)
    {
        int tmp = input[0];
        input[0] = input[len-1];
        input[len-1] = tmp;
    }

}