一个文件中有40亿个整数,每个整数为四个字节,内存为1GB,写出一个算法:求出这个文件里的整数里不包含的一个整数
答:方法一: 4个字节表示的整数,总共只有2^32约等于4G个可能。
为了简单起见,可以假设都是无符号整数。
分配500MB内存,每一bit代表一个整数,刚好可以表示完4个字节的整数,初始值为0。基本思想每读入一个数,就把它对应的bit位置为1,处理完40G个数后,对500M的'内存遍历,找出一个bit为0的位,输出对应的整数就是未出现的。算法流程:
1)分配500MB内存buf,初始化为0
2)unsigned int x=0×1;
for each int j in file
buf=buf ¦x < <j;
end
(3) for(unsigned int i=0; i <= 0xffffffff; i++)
if (!(buf & x < <i))
{
output(i);
break;
}
以上只是针对无符号的,有符号的整数可以依此类推。
腾讯笔试一题多解
文学乐
人气:3.09W
热门推荐
猜你喜欢
今日热门
- 1腾讯测试类实习笔试题
- 2腾讯笔试经验
- 32015腾讯web前端笔试题
- 4腾讯笔试题目及答案
- 5腾讯人力资源笔试题
- 6腾讯面试题
- 7腾讯笔试感受
- 8腾讯技术综合笔试题
- 9腾讯校园招聘笔试试题
- 10腾讯商业分析笔试题
- 11腾讯2012实习生笔试题
- 12腾讯测试强生的笔试题目
- 132016腾讯软件测试笔试题目
- 14腾讯笔试有感
- 15腾讯产品类笔试题目