腾讯PCG后台开发:3亿个整数,怎么找出所有只出现一次的数

我回答用2bit的bitmap处理,每个数出现一次为01,出现多次为11,未出现的为00,这样只需要3亿*2/8/1024/1024=71.5MB,但面试官让我再想想?
请问还有没有更好的方法?

内存我算错了,bitmap应该要覆盖到int的范围-20亿~20亿,所以内存大概要用1G。。。
#腾讯PCG##腾讯##笔试题目#
全部评论
可不可以用两个bitmap,一个表示没有重复数字的,一个用来标记重复数字的。第一个存3亿个整数的去重结果,在构建第一位图的过程中,如果判断某个数字是重复的,在构建第二个位图。最后将第一个位图和第二个位图的取反相与,得到的结果就是只出现一次的数字。
点赞 回复 分享
发布于 2020-04-12 18:22
只是整数么,那不就int类型,直接列一个int大小的数组,没多大吧,一个个遍历标记。
点赞 回复 分享
发布于 2020-03-21 17:13
一般答到位图法就差不多了吧,面试官有提示往哪方面优化吗?
点赞 回复 分享
发布于 2020-03-21 11:13
先求出最大值和最小值,离散化后,再用bitmap处理呢?
点赞 回复 分享
发布于 2020-03-21 11:05
会不会好点儿😂
点赞 回复 分享
发布于 2020-03-21 07:20
hash分一下,把3亿个整数分成1000份(或者更多),对每一份使用bitmap,最后合并起来使用bitmap
点赞 回复 分享
发布于 2020-03-21 07:20
异或运算
点赞 回复 分享
发布于 2020-03-21 01:33
这个内存是不是应该用2^32来算呀😕
点赞 回复 分享
发布于 2020-03-21 00:16
同pcg后台,问一下楼主一面和二面隔了多久啊😂我等二面等了3天了,是不是凉了
点赞 回复 分享
发布于 2020-03-21 00:10
同pcg,二面被问到10亿QQ号的和怎么加,我用了100个线程分10次加,但不知道什么数据结构可以放下100w个QQ号和,借楼问下,因为这个挂的,完全不知道怎么处理😂
点赞 回复 分享
发布于 2020-03-20 23:54

相关推荐

最近群里有很多同学找我看简历,问问题,主要就是集中在明年三月份的暑期,我暑期还能进大厂嘛?我接下来该怎么做?对于我来说,我对于双非找实习的一个暴论就是title永远大于业务,你在大厂随随便便做点慢SQL治理加个索引,可能就能影响几千人,在小厂你从零到一搭建的系统可能只有几十个人在使用,量级是不一样的。对双非来说,最难的就是约面,怎么才能被大厂约面试?首先这需要一点运气,另外你也需要好的实习带给你的背书。有很多双非的同学在一些外包小厂待了四五个月,这样的产出有什么用呢?工厂的可视化大屏业务很广泛?产出无疑是重要的,但是得当你的实习公司到了一定的档次之后,比如你想走后端,那么中厂后端和大厂测开的选择,你可以选择中厂后端(注意,这里的中厂也得是一些人都知道的,比如哈啰,得物,b站之类,不是说人数超过500就叫中厂),只有这个时候你再去好好关注你的产出,要不就无脑大厂就完了。很多双非同学的误区就在这里,找到一份实习之后,就认为自己达到了阶段性的任务,根本不再投递简历,也不再提升自己,玩了几个月之后,美其名曰沉淀产出,真正的好产出能有多少呢?而实际上双非同学的第一份实习大部分都是工厂外包和政府外包!根本无产出可写😡😡😡!到了最后才发现晚了,所以对双非同学来说,不要放过任何一个从小到中,从中到大的机会,你得先有好的平台与title之后再考虑你的产出!因为那样你才将将能过了HR初筛!我认识一个双非同学,从浪潮到海康,每一段都呆不久,因为他在不断的投递和提升自己,最后去了美团,这才是双非应该做的,而我相信大部分的双非同学,在找到浪潮的那一刻就再也不会看八股,写算法,也不会打开ssob了,这才是你跟别人的差距。
迷茫的大四🐶:我也这样认为,title永远第一,只有名气大,才有人愿意了解你的简历
双非本科求职如何逆袭
点赞 评论 收藏
分享
评论
1
30
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务