騰訊筆試一題多解
一個(gè)文件中有40億個(gè)整數(shù),每個(gè)整數(shù)為四個(gè)字節(jié),內(nèi)存為1GB,寫出一個(gè)算法:求出這個(gè)文件里的整數(shù)里不包含的一個(gè)整數(shù)
答:方法一: 4個(gè)字節(jié)表示的整數(shù),總共只有2^32約等于4G個(gè)可能,
騰訊筆試一題多解
。為了簡(jiǎn)單起見,可以假設(shè)都是無符號(hào)整數(shù)。
分配500MB內(nèi)存,每一bit代表一個(gè)整數(shù),剛好可以表示完4個(gè)字節(jié)的整數(shù),初始值為0;舅枷朊孔x入一個(gè)數(shù),就把它對(duì)應(yīng)的bit位置為1,處理完40G個(gè)數(shù)后,對(duì)500M的'內(nèi)存遍歷,找出一個(gè)bit為0的位,輸出對(duì)應(yīng)的整數(shù)就是未出現(xiàn)的。算法流程:
1)分配500MB內(nèi)存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;
}
以上只是針對(duì)無符號(hào)的,有符號(hào)的整數(shù)可以依此類推,