题解 | #最小的K个数#

利用的是堆排序算法

提前需要了解的知识点：

找出最后一个非叶子节点：(length-1)/2

获取一个父节点的子节点 ： (child*2)+1 、(child*2)+2

逻辑大致如下：

1、把列表改造成最小堆，也就是列表的第一个元素是最小值

（1）获取列表里的最后一个非叶子节点。把当前这个节点当作是一棵树，获取该节点下的最大堆。

a、获取列表里的最后一个非叶子节点。定位到这个非叶子节点的两个子节点。

b、判断两个子节点哪个是最小的。

c、把最小的子节点和父节点对比，加入子节点比父节点小，则把他们两替换一下

d、假如最小的子节点没有比父节点小，可以执行退出。

e、假如最小的子节点比父节点小，需要获取把子节点当作父节点，然后找出该节点是否子节点，若有的话，再次调到步骤a进行操作。

（2）for循环，获取前一个叶子节点，当作为父节点，把当前节点的子树如步骤（1）改成成最小堆。

2、把最小的值和列表最后一个值进行替换。

3、根据需要k个值，则循坏k次去获取列表中的最小堆，注意的是每次经过步骤2后，列表最后的k个值则不需要加入到列表排序中，也就是当作列表少了最后k个数。

4、获取最后k个数的值，则是列表中最小的K个值。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型一维数组 
     * @param k int整型 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        for(int i =input.length-1;i>input.length-1-k;i--)
        {
             getbiggest(input,i);
        }
        // int[] result = new int[k];
        ArrayList<Integer>  result= new ArrayList<>();

        for(int i = 0;i<k;i++)
        {
            result.add(input[input.length-1-i]);
        }
        return result;
    }


    private void getbiggest(int[] input,int length)
    {
        for(int i = (length-1)/2;i>=0;i--)
        {
            sort(input,i,length);
        }
        int tmp = input[length];
        input[length] = input[0];
        input[0]=tmp;
    }

    private void sort(int[] input, int father, int size)
    {
        //获取父节点的值
        int fatherValue = input[father];
        for(int child = (father*2)+1 ;child<=size; child=(child*2)+1)
        {
            //比较两个子节点、获取值最大的一个
            if(child<size &&  input[child]<input[child+1]){
                child++;
            }
            //比较最大的子节点和父节点
            if(input[child]>input[father])
            {
                int tmp = input[father];
                input[father] = input[child];
                input[child] = tmp;
                father=child;
            }
            else{
                break;
            }
        } 
    }
}

}