剑指offer-40

题目：最小的k个数

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

举例说明

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

思路

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

要求一个序列中最小的k个数，按照惯有的思维方式，则是先对这个序列从小到大排序，然后输出前面的最小的k个数。
至于选取什么的排序方法，我想你可能会第一时间想到快速排序（我们知道，快速排序平均所费时间为nlogn），然后再遍历序列中前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);
		}
	}
}