腾讯PCG后台开发：3亿个整数，怎么找出所有只出现一次的数
我回答用2bit的bitmap处理，每个数出现一次为01，出现多次为11，未出现的为00，这样只需要3亿*2/8/1024/1024=71.5MB，但面试官让我再想想?
请问还有没有更好的方法？
内存我算错了，bitmap应该要覆盖到int的范围-20亿～20亿，所以内存大概要用1G。。。
#腾讯PCG##腾讯##笔试题目#
2020-03-21 08:07 已编辑 华中科技大学 C++
关注
全部评论
无情派大星
大连理工大学 Java
同pcg，二面被问到10亿QQ号的和怎么加，我用了100个线程分10次加，但不知道什么数据结构可以放下100w个QQ号和，借楼问下，因为这个挂的，完全不知道怎么处理😂
买太平湖底陈年水墨
字节跳动_Infra_SG_研发工程师
同pcg后台，问一下楼主一面和二面隔了多久啊😂我等二面等了3天了，是不是凉了
Resolmi
门头沟学院 Java
这个内存是不是应该用2^32来算呀😕
zayin111111
中山大学 算法工程师
异或运算
买太平湖底陈年水墨
字节跳动_Infra_SG_研发工程师
hash分一下，把3亿个整数分成1000份（或者更多），对每一份使用bitmap，最后合并起来使用bitmap
买太平湖底陈年水墨
字节跳动_Infra_SG_研发工程师
会不会好点儿😂
练习写bug
北京大学 C++
先求出最大值和最小值，离散化后，再用bitmap处理呢?
菜饼同学
腾讯_AMS_后台开发
一般答到位图法就差不多了吧，面试官有提示往哪方面优化吗？
牛客966161000号
只是整数么，那不就int类型，直接列一个int大小的数组，没多大吧，一个个遍历标记。
进击小白
南京邮电大学 C++
可不可以用两个bitmap，一个表示没有重复数字的，一个用来标记重复数字的。第一个存3亿个整数的去重结果，在构建第一位图的过程中，如果判断某个数字是重复的，在构建第二个位图。最后将第一个位图和第二个位图的取反相与，得到的结果就是只出现一次的数字。
相关推荐
在刷代码的小确幸很讲义气：一点点来，运动减重早睡早起，情绪就会一点点稳定起来，别的问题都得慢慢改善） 点赞 评论 收藏
分享
11-11 15:12
南昌大学 材料工程师 
一个菜鸡罢了：哥们，感觉你的简历还是有点问题的，我提几点建议，看看能不能提供一点帮助
1. ”新余学院“别加粗，课程不清楚是否有必要写，感觉版面不如拿来写一下做过的事情，教育经历是你的弱势就尽量少写
2. “干部及社团经历”和“自我评价”删掉
3. 论文后面的“录用”和“小修”啥的都删掉，默认全录用，问了再说，反正小修毕业前肯定能发出来
4. 工作经验和研究成果没有体现你的个人贡献，着重包装一下个人贡献 点赞 评论 收藏
分享