首页 > 试题广场 >

给定100亿个整数，设计算法找到只出现一次的整数

[问答题]
给定100亿个整数，设计算法找到只出现一次的整数
查看答案及解析
添加回答
传奇的魅影头像 传奇的魅影
如果是有符号整数的话，范围为-2147483648~2147483647 无符号整数为0~4294967296 有符号的使用两个bitset,一个存放正数，一个负数。 每个数使用两个位来判断其出现几次。00表示出现0词，01出现1次，10出现大于一次。 比如说存放整数100，就将bitset的第100*2位设置为+1，当所有数放完之后，对每两位进行测试看其值为多少？若是第i为与i+1为的值为01，则这个整数：i*2，在集合中只出现了1次。需要总共用bitnun=(2^31*2)个位表示，需空间为int[bitnum],即512M.
发表于 2016-08-19 22:17:56 回复(2)
陈木木头像 陈木木
Hash分桶法，将100亿个整数映射到不同的区间，在每个区间中分别找只出现一次的整数
发表于 2015-05-05 14:57:27 回复(0)
江山如画君头像 江山如画君
使用hash将所有整数映射到1000个文件中，在每个文件中使用 bitmap，用两个bit表示出现次数，00表示没出现过，01表示出现过1次，10表示出现过多次，11舍弃，最后归并每个文件中出现只有1次的数即为所求。
发表于 2015-05-30 12:39:43 回复(0)
我嘞个天呐头像 我嘞个天呐
用bitmap表示数据，bitmap中每两位代表一个整数，00代表该整型未出现过，01代表出现过1次，11代表出现超过1次。最后只需输出01对应的整型即可。（优点：节省内存）
发表于 2019-03-31 15:06:52 回复(0)
你雕沙到我了头像 你雕沙到我了
可以使用hash桶或者位图
发表于 2018-09-17 21:10:17 回复(0)
bboyM头像 bboyM
用hashtable
编辑于 2015-07-25 22:18:38 回复(0)
小小娃爱吃甜食头像 小小娃爱吃甜食
hash分桶法
发表于 2015-07-11 16:20:29 回复(0)
提交观点

问题信息

复杂度 查找
上传者：陈木木
难度：
7条回答 10995浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号