腾讯笔试一题多解

腾讯笔试一题多解

　　一个文件中有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 &brvbar;x < <j;

　　end

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

　　if (!(buf & x < <i))

　　{

　　output(i);

　　break;

　　}

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

资料共享平台

《腾讯笔试一题多解》(https://www.unjs.com)。

【腾讯笔试一题多解】相关文章：

腾讯笔试经验分享07-03

腾讯运营笔试题10-08

腾讯校招笔试题08-08

腾讯北京营销笔试经验09-18

腾讯技术综合笔试题09-15

腾讯校招笔试题目08-07

腾讯游戏策划笔试题目07-21

腾讯技术类模拟笔试题09-09

腾讯软件测试常见笔试题07-21

腾讯广州游戏策划笔试经验10-04