问一道题，面试遇到的，不会
说的是有一亿条数据(假设里面是数字)，让我找出里面最大的五个数，我该怎么找，这些数据存在文件里，一行存一个。都不知道要考啥…我就说了一个一个读出来，再记录最大的五个数.答案肯定不是这个，不过确实不知道该往什么方向想，有带哥解答一下吗？感谢#题解#
2019-07-12 14:37 已编辑 门头沟学院 C++
关注
全部评论
刘文涛123
快手_国际化服务端架构开发_Java开发工程师
先问一亿条数据是否存在一个文件，如果是的话，就顺序读取，建立一个有5个元素的小根堆，没读取一个元素就和小根堆顶作比较，如果比小根堆顶小就继续读取，如果比小根堆定大，就替换小根堆顶元素，并且重新构建根堆，直到全部读取完。 如果存在几个文件中，则几个文件同时按照上述步骤进行，然后将所有小跟堆的数据整合，在从新进行小根堆操作。
呆小木
西安交通大学 数据分析师
这种题目一般有内存限制，思想就是分治。有两种方法，一种就是利用哈希把大文件拆分成若干个小文件，每个小文件都在内存限制范围之内，依次读入内存，配合小顶堆，就能找出最小的n个数。另外一种就是使用分布式集群，利用哈希把大文件映射到多台节点上，每台机器分别计算，最后汇总
纯情艳阳天
浙江大学 Java
用大小为5的小顶堆
你午睡了么🔯
北京邮电大学 Java
topn 大顶堆?
躺平大仙DiamondJ
南昌大学 Java
用mapreduce读?不太懂，等大神回答
多菜啊才这纠结半天？ 楼主
楼主 门头沟学院 C++
感谢牛友热心解答😁
七彩祥云吞天
京东_数据开发
分布式读取 哈哈
NowaCoder
阿里巴巴_阿里云_研发工程师
堆堆堆
池里游啊游
北京青年政治学院 Java
大顶堆或者把这些数据分成1000份，每份里面取最大的5个。然后再把取出来的50000个数据里面取最大的五个。这样内存就存的下了。
Leal.
The University of Sydney 大数据开发工程师
应该可以用 mapreduce或者 spark吧。就是topN的问题，可以用小顶堆
后端打杂人员
中国科学技术大学 C++
5只是个虚数，问题关键应该还是经典的TopK问题，5个元素的话用堆说实话不比数组有优势，1000个，10000个就差别明显了。
ssezhangpeng
百度_AIG_后台开发
局部淘汰法
相关推荐
投递快手等公司10个岗位 点赞 评论 收藏
分享