一個檔案中有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 < <j;
end
(3) for(unsigned int i=0; i <= 0xffffffff; i++)
if (!(buf & x < <i))
{
output(i);
break;
}
以上只是針對無符號的,有符號的整數可以依此類推。
騰訊筆試一題多解
文思屋
人氣:3.2W
熱門文章
最近更新
猜你喜歡
- 12015騰訊web前端筆試題
- 2騰訊人力資源筆試題
- 3騰訊筆試有感
- 4騰訊測試強生的筆試題目
- 52016騰訊軟體測試筆試題目
- 6騰訊測試類實習筆試題
- 7騰訊面試題
- 8騰訊2012實習生筆試題
- 9騰訊筆試感受
- 10騰訊技術綜合筆試題
- 11騰訊校園招聘筆試試題
- 12騰訊筆試題目及答案
- 13騰訊產品類筆試題目
- 14騰訊筆試經驗
- 15騰訊商業分析筆試題