题目40：最小的k个数

输入n个整数，找出其中最小的k个数。

举例说明

例如输入4 、5 、1、6、2、7、3 、8 这8 个数字，则最小的4个数字是1 、2、3 、4

思路

一. 排序法---时间复杂度O(nlogn)

要求一个序列中最小的k个数，按照惯有的思维方式，则是先对这个序列从小到大排序，然后输出前面的最小的k个数。
至于选取什么的排序方法，我想你可能会第一时间想到快速排序（我们知道，快速排序平均所费时间为n*logn），然后再遍历序列中前k个元素输出即可。因此，总的时间复杂度：O（n * log n)+O(k)=O（n * log n）。

二. 数组---时间复杂度O(nk)

咱们再进一步想想，题目没有要求最小的k个数有序，也没要求最后n-k个数有序。既然如此，就没有必要对所有元素进行排序。这时，咱们想到了用选择或交换排序，即：
1、遍历n个数，把最先遍历到的k个数存入到大小为k的数组中，假设它们即是最小的k个数；
2、对这k个数，利用选择或交换排序找到这k个元素中的最大值kmax（找最大值需要遍历这k个数，时间复杂度为O（k））；
3、继续遍历剩余n-k个数。假设每一次遍历到的新的元素的值为x，把x与kmax比较：如果x < kmax ，用x替换kmax，并回到第二步重新找出k个元素的数组中最大元素kmax‘；如果x >= kmax，则继续遍历不更新数组。
每次遍历，更新或不更新数组的所用的时间为O（k）或O（0）。故整趟下来，时间复杂度为nO（k）=O（nk）。

三. 大根堆---时间复杂度O(nlogk)

更好的办法是维护容量为k的最大堆(适合处理海量数据)，原理跟解法二的方法相似：

1. 用容量为k的最大堆存储最先遍历到的k个数，同样假设它们即是最小的k个数
2. 堆中元素是有序的，令k1<k2<...<kmax（kmax设为最大堆中的最大元素）
3. 遍历剩余n-k个数。假设每一次遍历到的新的元素的值为x，把x与堆顶元素kmax比较：
   3.1 如果x < kmax，用x替换kmax，然后更新堆（用时logk）
   3.2 否则不更新堆

这样下来，总的时间复杂度:O（k+（n-k）logk）=O（nlogk）。此方法得益于堆中进行查找和更新的时间复杂度均为：O(logk)（若使用解法二：在数组中找出最大元素，时间复杂度：O（k））。

代码实现

大根堆法

public class _40 {
    public static void printTopMinK(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k <= 0)
            return;
        for (int i = 0; i < k; i++) { // 建堆
            heapInsert(arr, i);
        }
        for (int i = k; i < arr.length; i++) { // 循环比较更新堆
            heapify(arr, i, k);
        }
        for (int i = 0; i < k; i++) {// 打印
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {// 是否取代父
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int size) {
        if (arr[index] > arr[0])
            return;
        swap(arr, 0, index);
        int cur = 0;
        int cand;
        while (cur < size) {
            cand = cur;
            if (cur * 2 + 1 < size && arr[cur * 2 + 1] > arr[cand])
                cand = cur * 2 + 1;
            if (cur * 2 + 2 < size && arr[cur * 2 + 2] > arr[cand])
                cand = cur * 2 + 2;
            if (cand == cur)
                break;
            else {
                swap(arr, cur, cand);
                cur = cand;
            }
        }
    }
    
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 1, 9, 2, 8, 3, 7, 4, 6, 5 };
        for (int i = 1; i <= arr.length; i++) {
            printTopMinK(arr, i);
        }
    }
}

最小的k个数