首页 > 试题广场 >

一个文本文件里面有100亿行无序的数据，将这些数据从小到大排

[问答题]
一个文本文件里面有100亿行无序的数据，将这些数据从小到大排列并输出前100个数据。
添加回答
神剑显锋头像 神剑显锋
由于这些数据没有规律，4G的内存一共是4 × 1000 × 1000 × 1000 = 1000000000 = 40亿字节，而此处需要占用内存100亿 × 4字节（假如是int型） = 400亿字节 = 40G，显然虚拟空间是不行的，因此，需要对这些数据分块处理。把这些数据分成1000份，然后再对这1000份数据分别进行排序，使用STL种的map结构，key为数据值，value为次数，按key排序，排序好后，放入一个文件中，然后对这1000份数据一个一个整合起来，取map中的前100个（按照value的值相加，比如key = 100000, value = 6,那么这个值就有6个了，剩下从map里面再取94个）就OK了。
编辑于 2015-04-11 22:37:17 回复(0)
AndyJee头像 AndyJee
数据分块、Hash映射、归并统计、堆排序
编辑于 2015-04-14 20:19:43 回复(0)
pcdesigner头像 pcdesigner
存放100个数据的大顶堆，先把前一百行放入，然后遍历后面的行，遇到比堆顶元素小的，替换，堆调整，继续下面的行。时间复杂度NlgK,N为100亿，K为100.
发表于 2015-04-11 16:10:31 回复(0)
向宇回桌头像 向宇回桌
归并排序呀~
发表于 2015-04-10 21:53:38 回复(0)
试试手气头像 试试手气
第一想法就是建立一个堆。。。。
发表于 2015-04-10 21:18:11 回复(0)
W.Y.><头像 W.Y.><
先用二叉排序树对这些数字进行排序，在进行先序遍历
发表于 2015-04-10 19:40:02 回复(0)
提交观点

问题信息

复杂度 堆 去哪儿
上传者：稻叶三千
难度：
6条回答 19412浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号