Top K 问题解法备份

经典问题：有n个数字（n<=10 000 000)，找出最小（或者最大）的K个（K=100）。

方法一：比较排序，nlogn，放弃。

方法二：如果数字各不相同，而且范围不大，可以考虑位图，时间和空间复杂度O(n)和O(n/64)=O(n)，但是如果是int那么遍历的次数比n大得多，放弃。

方法三：如果数字可以重复，考虑用字典，但是空间占用率太大，而且也会有遍历次数过多的问题，放弃。

方法四：堆。最坏的情况下复杂度O(nlogK)，K=100，貌似还可以接受。空间复杂度O(K)，已经很不错了，关键是实现简便，而且可以应对各种情况。

方法五：类似快速排序的分治法：随便选一个元素把数组分成左右两部分，并且把所有比这个元素大的放在左边，小的放在右边。如果这个基准元素左边正好有K个数字，就是所求的结果。否则：如果不足K个，那么递归拆分右侧的区间，最终结果就是左侧L个+右侧的K-L个；如果比K个多，则在左侧区间递归拆分。

这个算法的复杂度O(n)。简单来说可以这样估算：如果每次正好化成相等的两部分，第一次循环n次，第二次n/2次，第三次n/4次…… 求和就是O(n)。由于基准元素是随机选的，所以不太可能出现最坏的情况。

关于选择基准元素，做法和快速排序类似：

• 随机选择一个：这个效果貌似是比较好的。
• 选择最左侧或者最后测的元素：如果数组基本有序那么复杂度会变成O(n^2)，所以一般不这么做。
• 左侧、右侧和中间元素选择一个中间数，M$的Sort代码是这样写的，效果应该和随机选相当。

	private static int[] internalFindTopK(int[] a, int left, int right) {
		int p = new Random().nextInt(right - left + 1) + left;
		int n = a[p];
		
		int temp = a[right];
		a[right] = n;
		a[p] = temp;
		
		int i = left, j = right - 1;
		
		while (i < j) {
			while (i < j && a[i] < n)
				i++;
			
			while (i < j && a[j] > n)
				j--;
			
			if (i < j) {
				temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		
		temp = a[i];
		a[i] = n;
		a[right] = temp;
		
		if (i == K - 1) {
			int[] result = new int[K];
			System.arraycopy(a, 0, result, 0, K);
			
			return result;
		} else if (i < K - 1)
			return internalFindTopK(a, i + 1, right);
		else
			return internalFindTopK(a, left, i - 1);
		
		
	}
	
	public static int[] findTopK(int[] a) {
		return internalFindTopK(a, 0, a.length - 1);
	}