2 lulinha lulinha 于 2014.12.12 22:01 提问

去哪儿网面试题:对100亿行数据排序

一个文本文件里面有100亿行无序的数据,将这些数据从小到大排列并输出前100个数据。

http://www.manong1024.com/q/205

4个回答

caozhy
caozhy   Ds   Rxr 2014.12.12 23:44

这是典型的bitmap排序。也就是创建一个4294967296元素的数组,然后遍历这100亿数据,如果某个数据等于12,就让数组下标为12的那个元素+1,以此类推。
最后从数组0开始输出,如果这个元素对应的值是1,就输出1次,如果是2就输出2次,直到100为止。

lx624909677
lx624909677   Ds   Rxr 2014.12.13 10:50

如果用bitmap排序,那有重复数据怎么办

caozhy
caozhy 重复没有关系。每个数组元素用一个int表示,可以让它累加。如果超过了int的上限,置-1,然后用一个稀疏字典存储。
大约 3 年之前 回复
xuzuning
xuzuning   Ds   Rxr 2014.12.14 09:10

你只取小端的 100 个数据,所以只需开辟 100个元素的链表就可以了
遍历这100亿数据,有序的插入结果链表(溢出时丢弃)

oyljerry
oyljerry   Ds   Rxr 2015.01.06 22:31

位图隐射,然后遍历。
回或者小根堆

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!