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

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

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

相关推荐

点赞 评论 收藏
分享
1 30 评论
分享
牛客网
牛客企业服务