关注
67.假设1亿的11位的手机号,运行空间128M,如果要进行排序,那么要怎么设计:
本问题中,可以借鉴归并排序的思路,将大文件拆成100个小文件,小文件内部排好序,然后进行100路的归并操作。
步骤
将 1. G的大文件,经过一遍按行读写的方式(迭代器模式)进行处理,拆成 100 100 100个小文件,每个小文件中存放100万个手机号。
分别将100个小文件读进内存,将手机号从小到大排序,排序结果写回对应的小文件中。
通过一个小顶堆形式的优先级队列(PriorityQueue)进行归并操作。堆中的元素是一个二元组:(手机号, 该手机号对应的小文件编号)。
一开始,将每个文件的第一个手机号读出来放到小顶堆中。由于这 100 100 100个手机号分别是各个子文件中最小的,因此,此时小顶堆堆顶的手机号就是全局最小的手机号。因此可以将堆顶元素弹出,写到最终的输出文件mobiles_sorted.txt中。
每次从堆顶弹出一个元素后,如果该元素所对应的小文件还没被处理完,就从相应小文件中读入下一个手机号,补充到堆中。
所有手机号都各自加入和弹出小顶堆一次后,排序完成,此时的mobiles_sorted.txt文件就是最终结果
查看原帖
点赞 评论
相关推荐
11-14 16:03
西北政法大学 新媒体运营 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 找工作能把i人逼成什么样 #
14684次浏览 174人参与
# 上班到公司第一件事做什么? #
109377次浏览 740人参与
# 你今年做了几份实习? #
9776次浏览 145人参与
# 工作两年想退休了 #
203426次浏览 1799人参与
# 你开始找寒假实习了吗? #
15898次浏览 210人参与
# 新凯来求职进展汇总 #
64127次浏览 171人参与
# 影石Insta360求职进展汇总 #
166505次浏览 1335人参与
# 大厂面试初体验 #
83630次浏览 385人参与
# 0经验如何找实习? #
27047次浏览 456人参与
# 面试尴尬现场 #
205404次浏览 821人参与
# 大学最后一个寒假,我想…… #
72260次浏览 726人参与
# 25届秋招公司红黑榜 #
306651次浏览 1252人参与
# 什么样的公司千万别去 #
28026次浏览 148人参与
# 大家每天通勤多久? #
64497次浏览 415人参与
# 金融财经春招备战日记 #
43896次浏览 216人参与
# 央国企投递记录 #
166052次浏览 1622人参与
# 你找工作经历过哪些骗局? #
9730次浏览 144人参与
# 机械人值得去的半导体企业 #
32983次浏览 183人参与
# 字节出了豆包coding模型 #
6874次浏览 61人参与
# 一起聊华为 #
168560次浏览 820人参与
360集团公司福利 438人发布