騰訊筆試一題多解
一個(gè)文件中有40億個(gè)整數，每個(gè)整數為四個(gè)字節，內存為1GB，寫(xiě)出一個(gè)算法：求出這個(gè)文件里的整數里不包含的一個(gè)整數
答:方法一: 4個(gè)字節表示的整數，總共只有2^32約等于4G個(gè)可能。
為了簡(jiǎn)單起見(jiàn)，可以假設都是無(wú)符號整數。
分配500MB內存，每一bit代表一個(gè)整數，剛好可以表示完4個(gè)字節的整數，初始值為0�；舅枷朊孔x入一個(gè)數，就把它對應的bit位置為1，處理完40G個(gè)數后，對500M的'內存遍歷，找出一個(gè)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;
}
以上只是針對無(wú)符號的，有符號的整數可以依此類(lèi)推。
【騰訊筆試一題多解】相關(guān)文章：
小學(xué)生一題多解應用題10-06
2017騰訊筆試題07-21
騰訊技術(shù)筆試題12-20
騰訊運營(yíng)筆試題12-20
騰訊筆試題目初試11-13
騰訊前端筆試題目01-15
騰訊商業(yè)分析筆試題06-28
騰訊校招筆試題01-16
騰訊技術(shù)筆試題目01-16
騰訊技術(shù)綜合筆試題01-15