這是一個面試問題：給定一個包含40億個整數(shù)的輸入文件，提供一個算法來生成一個未包含在文件中的整數(shù)。假設(shè)您有1 GB內(nèi)存。如果您只有10 MB內(nèi)存，請跟進(jìn)您的操作。我的分析：文件大小為4×10 9 ×4字節(jié)= 16 GB。我們可以進(jìn)行外部排序，因此我們可以了解整數(shù)的范圍。我的問題是在排序的大整數(shù)集中檢測缺失整數(shù)的最佳方法是什么？我的理解（閱讀完所有答案后）：假設(shè)我們正在討論32位整數(shù)。有2 ^ 32 = 4 * 10 9個不同的整數(shù)。情況1：我們有1 GB = 1 * 10 9 * 8位= 80億位內(nèi)存。解決方案：如果我們使用一個代表一個不同整數(shù)的位，那就足夠了。我們不需要排序。執(zhí)行：int radix = 8;byte[] bitfield = new byte[0xffffffff/radix];void F() throws FileNotFoundException{    Scanner in = new Scanner(new FileReader("a.txt"));    while(in.hasNextInt()){        int n = in.nextInt();        bitfield[n/radix] |= (1 << (n%radix));    }    for(int i = 0; i< bitfield.lenght; i++){        for(int j =0; j<radix; j++){            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);        }    }}情況2：10 MB內(nèi)存= 10 * 10 6 * 8位= 8000萬位解決方案：對于所有可能的16位前綴，有2 ^ 16個整數(shù)= 65536，我們需要2 ^ 16 * 4 * 8 = 2百萬位。我們需要構(gòu)建65536個桶。對于每個桶，我們需要4個字節(jié)來保存所有可能性，因為最壞的情況是所有40億個整數(shù)屬于同一個桶。通過第一次通過文件構(gòu)建每個桶的計數(shù)器。掃描存儲桶，找到第一個命中率低于65536的存儲桶。構(gòu)建新的存儲桶，我們在第二步中通過文件的第二次傳遞找到了高16位前綴掃描步驟3中構(gòu)建的存儲桶，找到第一個沒有命中的存儲桶。代碼與上面的代碼非常相似。結(jié)論：我們通過增加文件傳遞來減少內(nèi)存。對那些遲到的人的澄清：問題，并不是說文件中沒有包含一個完整的整數(shù) - 至少不是大多數(shù)人解釋它的方式。但是，評論主題中的許多評論都是關(guān)于任務(wù)的變化。不幸的是，將其引入評論主題的評論后來被其作者刪除了，所以現(xiàn)在看起來孤立的回復(fù)只是誤解了一切。這很令人困惑。抱歉。