十亿手机号排序问题

tx面试官问十亿手机号要排序,然后我回答说用mapreduce,先分区排,再归并。然后面试官问我reduce怎么实现,我就跟他说最正常的归并排序算法,然后面试官说给我两个提示,一个是手机号都是十一位,还有一个是指针偏移量,最后没想出来,想问问大家面试官想听到什么回答。
全部评论
基数排序O(n)。先根据第11位排序(计数排序或者桶排序),再根据第10位排序,依次类推,最后一次是根据第一位重新排序。
1 回复 分享
发布于 2020-08-21 17:05
我感觉是位图?遍历一遍手机号,对应位置一就行
点赞 回复 分享
发布于 2020-08-21 16:44
手机号码的区间就是00000000000 - 99999999999,弄一个100000000000的区间,把数放到对应的地址位上,在按顺序取出来?
点赞 回复 分享
发布于 2020-08-21 16:56
用一个哈希函数,计算每个电话号码的hash值,然后对1000取余,这样可以把10 亿的电话号码分为1000分,存到1000个文件里面去,然后每个文件里面有100万数据,直接进行排序,然后用小根堆,相当于对多个排序好的链表进行排序。
点赞 回复 分享
发布于 2020-08-21 18:15
面试官明显想听到位图排序
点赞 回复 分享
发布于 2020-08-21 18:20

相关推荐

10-15 16:27
门头沟学院 C++
LeoMoon:建议问一下是不是你给他付钱😅😅
点赞 评论 收藏
分享
10-15 10:57
已编辑
武昌理工学院 FPGA工程师
狠赚笔第一人:老哥学院本没实习还想拿13k学Java狠赚笔呢
点赞 评论 收藏
分享
评论
点赞
6
分享
牛客网
牛客企业服务