首页 > 试题广场 >

1个文件有100亿个int，1G内存，设计算法找到出现次数不

[问答题]
1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数?
查看答案及解析
添加回答
逗逼邱奇头像 逗逼邱奇
首先位图法肯定没错，用两位表示数出现的次数，00表示未出现，01表示出现1次，10表示出现两次，11表示两次以上。然后扫描100亿个数，查看位图中对应的位置，如果是00,01,10，则加1变成01,10,11；如果是11，则不变。最后再扫描一遍位图，输出01，10对应的数。  2^32 * 2 = 8Gbits = 1GB。
发表于 2018-04-03 15:18:09 回复(3)
/*起一个响亮的名字吧*/头像 /*起一个响亮的名字吧*/
先hash到多个文件中，每个文件中的整数用位图表示，一个字节就可以表示4个整数。最后把每个文件中不超过两次的整数和在一起就是答案。
发表于 2015-08-20 16:50:46 回复(2)
陈木木头像 陈木木
Bitmap扩展：用2个bit表示状态，0未出现过，1出现过1次，2出现了2次或以上
编辑于 2015-05-18 13:20:48 回复(2)
提交观点

问题信息

高级结构
上传者：陈木木
难度：
3条回答 6696浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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