猿问

关于10G 个整数找出中位数,内存限制为 2G题目。

腾讯有这么一道校招题:
只有2G内存的pc机,在一个存有10G个整数的文件,从中找到中位数,写一个算法。

有好几种解法,比如桶排序和基数排序,但是我查到有个利用堆来解决的方法,不太明白,原话是这么说的:
先求第1G大,然后利用该元素求第2G大,然后利用第2G大,求第3G大...当然这样的话虽不需排序,但是磁盘操作会比较多,具体还需要分析下与外排序的效率哪个的磁盘IO会比较多
建立一个1g个整数的最大值堆,如果元素小于最大值则入堆,这样可以得到第1g大的那个元素然后利用这个元素,重新建一次堆,这次入堆的条件还要加上大于这个第1g大的元素,这样建完堆可以得到第2g大的那个。

看的我一头雾水不得其法,先求1G大都没看明白是什么,是把10G的数据分成10份,然后把其中1G里的排序找出最大的意思么?
希望大家能指点我下这个解决方法的思路,谢谢了。


慕村225694
浏览 736回答 1
1回答
随时随地看视频慕课网APP

相关分类

JavaScript
我要回答