题解 | #最小的K个数#

jz29:给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。如果K>数组的长度，那么返回一个空的数组
Java的Arrays类中的sort()方法对数组进行排序：
Arrays.sort(int[] a)
对一个数组的所有元素按从小到大进行排序
Arrays.sort(int[] a, int fromIndex, int toIndex)

对数组部分元素排序，也就是对数组a的下标从fromIndex到toIndex-1的元素排序
版本1：

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
         ArrayList<Integer> output=new ArrayList<>();
        if(k>input.length){
            //k>数组input的长度时返回一个空数组
            return output;
        }
        //Arrays.sort(int[] a)对一个数组的所有元素按从小到大进行排序
        Arrays.sort(input);
        for(int i=0;i<k;i++){
            output.add(new Integer(input[i]));
        }
        return output;
    }
}

堆排序：
堆排序，复杂度是o(nlogn)，比较稳定适合大数据量的排序，如果是快排的话大数据量容易引起OOM

堆通常是一个可以被看作一棵完全二叉树的数组
堆分为大顶堆和小顶堆

大顶堆：对于每一个节点，它都大于它的左孩子和右孩子
小顶堆：对于每一个节点，它都小于它的左孩子和右孩子
假如堆顶元素root的下标是从0开始的，那么对于某一个节点（下标为index），左孩子L（下标为2index+1），右孩子R（下标为2index+2）

选用大顶堆：
使用k个节点维护大顶堆
题中要求最小的四个数字（即维护k个节点的大顶堆）
就选取数组中四个数字（4,5,1,6）去组成四个节点的大顶堆
然后遍历剩下的N-k个数据，选出小于root的元素替换root，并维护堆为大顶堆

维护一个堆让它成为一个大顶堆方法：
自底向上从非叶子节点下标开始维护（非叶子节点下标=节点个数/2-1）
示例：
（3为非叶子结点 4,5,6,7为叶子结点）

第一次维护：非叶子结点6和它的左孩子8比较，8大，互换位置（将大的数往上层换）

第二次维护：节点1和它的左孩子7（选取孩子节点中最大的）比较，7大，互换位置

第三次维护：节点5和它的左孩子8比较，8大，互换位置；此时节点5的左孩子6又比节点5大，再互换位置

第四次维护：节点4和它的左孩子8比较,8大，互换位置；此时节点4的左孩子6又比节点4大，互换位置；接着节点4的左孩子5又比节点4大，再互换位置


遍历剩下的len-k个数据
如果当前位置数据小于堆顶元素root，用该数据替换root，然后维护堆让它成为一个大顶堆
将大顶堆中节点元素进行升序操作：
将堆顶元素与最后一个元素交换位置（这最后一个元素以后不会参加到堆的维护当中）

 import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (k > input.length || k == 0) {
            //返回空对象
            return new ArrayList<>();
        }

        int[] a = new int[k];//1.用数组模拟k个节点的大顶堆（堆通常是一个可以被看作一棵完全二叉树的数组）
//        for(int i=0;i<k;i++){
//            a[i]=input[i];
//        }
        //等同于
        //初始化堆中元素
        System.arraycopy(input, 0, a, 0, k);//从input数组中下标为0的数据开始复制k个数据到a数组从下标为0开始的位置，即intput[0]..input[k-1]复制到a[0]..a[k-1]
        //2.维护堆让它成为一个大顶堆
        //自底向上从非叶子节点下标开始维护（非叶子节点下标=节点个数/2-1）
        for (int i = k / 2 - 1; i >= 0; i--) {
            //维护大顶堆：非叶子结点和它的最大的孩子节点比较，孩子节点大，就互换位置（将大的数往上层换）
            initiate(i, a, k);
        }
        //3.遍历剩下的len-k个数据
        //如果当前位置数据小于堆顶元素root，用该数据替换root，然后维护堆让它成为一个大顶堆
        for (int i = k; i < input.length; i++) {
            //当前元素小于root
            if (input[i] < a[0]) {//a[0]:堆顶元素root
                a[0] = input[i];
                initiate(0, a, k);
            }
        }
        //4.将大顶堆中节点元素进行升序操作
        for(int i=a.length-1;i>0;i--){
            //将堆顶元素与最后一个元素交换位置（这最后一个元素以后不会参加到堆的维护当中）
            int temp=a[i];
            a[i]=a[0];
            a[0]=temp;
            initiate(0,a,i);
        }
        ArrayList<Integer> ans = new ArrayList<>();
        for(int x:a){
            ans.add(x);
        }
        return ans;
    }

    private void initiate(int index, int[] a, int k) {
        //假如堆顶元素root的下标是从0开始的，那么对于某一个节点（下标为index），左孩子L（下标为2*index+1），右孩子R（下标为2*index+2）
        //index维护当前堆的下标

        int temp=a[index];//保存当前位置的值
        for(int in=2*index+1;in<k;in=2*in+1){
            if(in+1<k && a[in+1]>a[in]){
                //a[in]左孩子 a[in+1]右孩子
                //取出当前位置的左右孩子中最大的一个
                in++;
            }
            //比较当前位置值与其最大孩子节点值，孩子节点大就互换位置
            if(a[in]>temp){//a[7]=8>a[3]=6
                a[index]=a[in];//换值//a[3]=8
                index=in;//换下标，
            }else{
                break;
            }
        }
        a[index]=temp;//a[7]=6
    }
}