騰訊相關筆試一題多解

騰訊相關筆試一題多解

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

　　}

　　以上只是針對無符號的，有符號的整數可以依此類推。

 

【騰訊相關筆試一題多解】相關文章：

小學生一題多解應用題10-06

2017騰訊筆試題07-21

騰訊技術筆試題12-20

騰訊運營筆試題12-20

騰訊前端筆試題目01-15

騰訊商業分析筆試題06-28

騰訊校招筆試題01-16

騰訊技術筆試題目01-16

騰訊技術綜合筆試題01-15

騰訊筆試題目初試11-05