经典问题:有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); }
大木这几天博客高产啊!
赞赞