蔡不菜和他的uU们

  • 首页
  • 新鲜出炉
  • 我的记录
  • 我的动态
  • 我和uU
  • 好用分享
  • 关于与留言
志合者,不以山海为远;道乖者,不以咫尺为近
  1. 首页
  2. 算法与数据结构
  3. 正文

40亿个QQ号码如何去重?

2022年6月11日 197人阅读 0人点赞 0条评论

问题引入

文件中有40亿个QQ号码,请设计算法对QQ号码去重,相同的QQ号码仅保留一个,内存限制1G.

问题的变型:42亿QQ,O(1)时间复杂度完成查找

问题思路

排序

经过排序后,相同的QQ号前后相邻,然后遍历一遍就可去重了。
但排序的最好效率 nlgn,在面对如此大的数据规模,运行时间也会很长,且有内存限制

Set

涉及到去重问题,我们第一时间想到的可能就是set了,以Java的HashSet为例,其底层实现为 数组 + 链表 + 红黑树,其还是涉及到存储问题,40亿的QQ号(最大为13位)已经超过了int 范围,直接存储的话,空间要求还是无法满足

位图 bitmap

其一个位置代表一个数,即一个下标也就是一个数,,这样一位就可以代表一个数,存储空间也可以满足要求
40亿 = 4,000,000,000 bit
   1G = 8,589,934,592 bit

值 0/1 代表了这个数存不存在,也就自动实现了去重。

参考

[1] 腾讯三面:40 亿个 QQ 号码如何去重? https://zhuanlan.zhihu.com/p/442732557

标签: 算法与数据结构;
最后更新:2022年6月11日

Csy

这个人很懒,什么都没留下

点赞
下一篇 >

文章评论

取消回复
文章目录
  • 问题引入
  • 问题思路
    • 排序
    • Set
    • 位图 bitmap
  • 参考

COPYRIGHT © 2021 caibucai.top. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

豫ICP备2021018055号