100亿个数取出最大的10000个

作者: veaxen 分类: 笔试面试 发布时间: 2017-07-27 16:08

题目:100亿个整数,求最大的1万个数,并说出算法的时间复杂度  

思路:
如果把100亿个数全部读入内存,需要100 0000 0000 * 4B 大约40G的内存,这显然是不现实的。我们可以在内存中维护一个大小为10000的最小堆,每次从文件读一个数,与最小堆的堆顶元素比较,若比堆顶元素大,则替换掉堆顶元素,然后调整堆。

最后剩下的堆内元素即为最大的1万个数,算法复杂度为O(NlogN)

实现:
从文件读数据有讲究,如果每次只读一个数,效率太低,可以维护一个输入缓冲区,一次读取一大块数据到内存,用完了又从文件接着读,这样效率高很多,缓冲区的大小也有讲究,一般要设为4KB的整数倍,因为磁盘的块大小一般就是4KB。

主要就是维护一个小根堆

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

一条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.