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);
	}

 

Top K 问题解法备份”的一个响应

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s