腾讯相关笔试一题多解

　一个文件中有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;

　　}

　　以上只是针对无符号的，有符号的整数可以依此类推。

 

　
• 上一篇：中国网通天津区笔试题
　

《腾讯相关笔试一题多解》相关文章

• 腾讯相关笔试一题多解
• › 腾讯相关笔试一题多解
• 在百度中搜索相关文章：腾讯相关笔试一题多解
• 在谷歌中搜索相关文章：腾讯相关笔试一题多解
• 在soso中搜索相关文章：腾讯相关笔试一题多解
• 在搜狗中搜索相关文章：腾讯相关笔试一题多解