腾讯笔试一题多解

腾讯笔试一题多解

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

　　(3) for(unsigned int i=0; i <= 0xffffffff; i++)

　　if (!(buf & x <
　　{

　　output(i);

　　break;

　　}

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