腾讯有这么一道校招题:
只有2G内存的pc机,在一个存有10G个整数的文件,从中找到中位数,写一个算法。
有好几种解法,比如桶排序和基数排序,但是我查到有个利用堆来解决的方法,不太明白,原话是这么说的:
先求第1G大,然后利用该元素求第2G大,然后利用第2G大,求第3G大...当然这样的话虽不需排序,但是磁盘操作会比较多,具体还需要分析下与外排序的效率哪个的磁盘IO会比较多
建立一个1g个整数的最大值堆,如果元素小于最大值则入堆,这样可以得到第1g大的那个元素然后利用这个元素,重新建一次堆,这次入堆的条件还要加上大于这个第1g大的元素,这样建完堆可以得到第2g大的那个。
看的我一头雾水不得其法,先求1G大都没看明白是什么,是把10G的数据分成10份,然后把其中1G里的排序找出最大的意思么?
希望大家能指点我下这个解决方法的思路,谢谢了。
堆是一种数据结构,是一棵完全二叉树(故保存其结构并不需要指针),每一个结点不大于或是不小于其子节点,分别对应大顶堆和小顶堆。比如,在小顶堆里面,根元素是最小的。所以其可以以
O(1)
的复杂度查找其中的最大或是最小的元素。其删除和插入元素的复杂度,最坏情况下都是O(log(N))
。这段话的意思是是说,先创建一个可以容纳(1G+1)个数据的小顶堆,即可以很快的找出其中的最小元素。然后遍历所有10G的数据,将其插入:如果插入后堆满了(堆中有了1G+1个数据)。就删除最小的那个。。。。
这样最后的结果就是,堆中的数据是最大的前 1G 个数据,并且堆顶是最小的那个,即如果降序排序,这个数据的位置是第1G的位置,比如这个数是 x。
然后,重新继续上述过程,但不同的是,只在堆中插入小于 x 的元素,忽略大于等于 x 的元素。即忽略刚才找出的那1G数据之后,在找出1G最大的。这样最终堆顶就是排序后第 2G 位置的数据。(但是要注意处理重复的数据)。。。。依次类推找出中位数。
我就有一个疑问,这种题难道不能用位图来做。。。
1、遍历这10G个数字,在位图里做标记哪些出现过,同时统计具体出现过多少个不同的数字,记为count
2、遍历位图,找到第 count/2 个bit,就是这个数。。。
如果整数是 0 ~ 2^32-1这种4byte的。那么存下它的取值范围,只需要512M内存的位图吧。。。。?
关于这个方法我还有些发散的问题,如果大神们觉得有意思可以看一下:
既然分成了10个堆,那么普遍情况每个堆的边界值是多少?
分成十堆的话,最差情况下快速排序需要多少次判断?
是否还可以减少计算量?
@zonxin