【剑指offer】-29-最小的k个数

1. 异常值分析，再Arrays.sort数组排序后输出前k个

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
     public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list= new ArrayList<>();
         if(k>input.length || input.length==0) return list;
        Arrays.sort(input);
        for(int i=0;i<k;i++){
            list.add(input[i]);
        }
        return list;
    }
}

2. 利用堆

• 堆是一个完全二叉树的数组，用数组表示堆并初始化，形成大根堆要不断维护堆中的节点，并且从最后一个非叶子节点（length/2-1）开始从下往上维护。

• 对于n个整数中最小的K个数的查找，可以使用各种排序算法：冒泡/堆排/快排/希尔排序等等。将此n个整数从小到大排序之后，前k个数就是所求的结果。

• 但是当原数组中的数据顺序不可修改，并且n的值过于大的时候，各种排序算法要将n个数加载到内存中，即：如果是海量数据中查找出最小的k个数，那么这种办法是效率很低的。接下来介绍另外一种算法：

• ** 创建一个大小为k的数组，遍历n个整数，如果遍历到的数小于大小为k的数组的最大值，则将此数与其最大值替换。**

• 由于每次都要拿n个整数和数组中的最大值比较，所以选择大根堆这一数据结构(大家要分清楚大根堆这一数据结构和堆排序之间的区别：堆排序是在大根堆这一数据结构上进行排序的一种排序算法，一个是数据结构，一个是算法)

  public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (k > input.length || input.length == 0 || k == 0) return list;
        int[] a = new int[k];//大顶堆实际上是一个完全二叉树的数组，所以用数组来初始化大顶堆
        if (k >= 0) System.arraycopy(input, 0, a, 0, k);//大顶堆初始化为input的前k个数
        int x = k / 2 - 1;//最后一个非叶子节点
        //从最后一个非叶子节点开始从下往上维护大顶堆
        for (int i = x; i >= 0; i--) {
            initiate(a, k, i);
        }
  
        // 去遍历剩余的len - k个节点
        for (int i = k; i < input.length; i++) {
            if (input[i] < a[0]) {
                a[0] = input[i];
                initiate(a, k, 0);
            }
        }
  
        //调整大顶堆为升序数组再输出
        for (int i = a.length - 1; i > 0; i--) {
            int temp = a[i];
            a[i] = a[0];
            a[0] = temp;
            initiate(a, i, 0);//再维护大顶堆
        }
  
        for (int value : a) {
            list.add(value);
        }
        return list;
    }
  
    /**
     * 初始化堆的函数，就是维护每一个节点的位置的函数
     *
     * @param a   数组->堆
     * @param len 堆的个数
     * @param x   要维护的节点的下标
     */
    private void initiate(int[] a, int len, int x) {
        int temp = a[x];
        for (int k = 2 * x + 1; k < len; k = k * 2 + 1) {
            if ((k + 1) < len && a[k + 1] > a[k]){ // 一定是(k + 1) < len 在左边，因为&&短路与，如果左边的条件不成立，那么不会执行右边，否则可能会有异常！！
                //找到左右孩子的最大值的下标k
                k++;
            }
            if (a[k] > temp) {
                a[x] = a[k];
                x = k;
            } else {
                break;//跳出for循环
            }
        }
        a[x] = temp;
    }

3. 插入排序，对前k个元素从小到大排序，迭代更新前k个元素

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer> result = new ArrayList<Integer>();
        if(k<= 0 || k > input.length)return result;
        //初次排序，完成k个元素的排序
        for(int i = 1; i< k; i++){
            int j = i-1;
            int unFindElement = input[i];
            while(j >= 0 && input[j] > unFindElement){
                input[j+1] = input[j];
                j--;
            }

            input[j+1] = unFindElement;
        }
        //遍历后面的元素 进行k个元素的更新和替换
        for(int i = k; i < input.length; i++){
            if(input[i] < input[k-1]){
                int newK = input[i];
                int j = k-1;
                while(j >= 0 && input[j] > newK){
                    input[j+1] = input[j];
                    j--;
                }
                input[j+1] = newK;
            }
        }
        //把前k个元素返回
        for(int i=0; i < k; i++)
            result.add(input[i]);
        return result;
    }
}

Top K问题参考：https://www.cnblogs.com/ccdev/archive/2012/09/12/2682246.html