剑指Offer第二十九题：最小的K个数

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

解答：
一种比较常见的思路就是先排序后取出前k位数字，这其中有各类排序算法都适用。比如冒泡排序，每一次遍历结束都可以定位一个最小值，这样就只需要k次遍历。

另一种思路是利用大根堆这种结构，先把前k位数字建立一个大根堆，然后对后n-k个数依次遍历。如果当前数值小于堆顶的值则替换堆顶的值，然后对大根堆做向下调整。
public class Q_29 {

public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
    ArrayList<Integer> list = new ArrayList<>();
    if (k > input.length || k == 0) {
        return list;
    }
    int len = input.length;
    creatBigHeap(input, k);//建立大根堆
    for (int i = k; i < len; i++) {
        if (input[i] < input[0]) {
            int tmp = input[i];
            input[k] = input[0];
            input[0] = tmp;
            ajustDown(input, 1, k);
        }
    }

    for (int j = 0; j < k; j++) {
        list.add(input[j]);
    }
    return list;
}

public int[] creatBigHeap(int[] A, int len) {
    for (int i = A.length / 2; i > 0; i--) {
        ajustDown(A, i, len);
    }
    return A;
}

private void ajustDown(int[] a, int i, int length) {//用递归的方法向下调整
    if (i * 2 <= length) {
        int tmp = a[i * 2 - 1];
        if (a[i - 1] < a[i * 2 - 1]) {
            if (i * 2 + 1 <= length && a[i * 2 - 1] < a[i * 2]) {
                tmp = a[i * 2];
                a[i * 2] = a[i - 1];
                a[i - 1] = tmp;
                ajustDown(a, i * 2 + 1, length);
            } else {
                a[i * 2 - 1] = a[i - 1];
                a[i - 1] = tmp;
                ajustDown(a, i * 2, length);
            }
        } else {
            if (i * 2 + 1 <= length && a[i - 1] < a[i * 2]) {
                tmp = a[i * 2];
                a[i * 2] = a[i - 1];
                a[i - 1] = tmp;
                ajustDown(a, i * 2 + 1, length);
            }
        }

    }
}

public static void main(String[] args) {
    int[] a = {53, 17, 78, 9, 45, 65, 87, 32};
    System.out.println(new Q_29().GetLeastNumbers_Solution(a, 4));
}

}