1.從40個億中產(chǎn)生一個不存在的整數(shù)
題目要求：給定一個輸入文件，包含40億個非負(fù)整數(shù)，請設(shè)計一個算法，產(chǎn)生一個不存在該文件中的整數(shù)，假設(shè)你有1GB的內(nèi)存來完成這項任務(wù)。****
解題中心思想：存儲的不是這40億個數(shù)據(jù)本身，而是其對應(yīng)的位置。
本題不用寫代碼，能把方法過程說清楚就可以。
1.1 位圖存儲大數(shù)據(jù)的原理
方法：8 bit 為 1B，一個32位整數(shù)需要4B的存儲空間，40億個數(shù)就是 40億 * 4B，約為16GB，用位圖來做的話會更節(jié)省空間，因為位圖的每個位置只能用0或1進(jìn)行狀態(tài)表示，這樣就只需要40億 / 8 = 5億字節(jié)，也就是大約500M的存儲空間。
過程：具體來做就是先遍歷這40億個數(shù)，并把遍歷的每個數(shù)在位圖上的相對位置設(shè)置為1。這40億個數(shù)遍歷結(jié)束后，開始遍歷位圖，看看哪個位置上的狀態(tài)為0，就說明這個位置對應(yīng)的數(shù)沒有在40億個數(shù)中出現(xiàn)，位圖遍歷結(jié)束后就能得到所有未在40億個數(shù)中出現(xiàn)過的數(shù)。
1.2 使用10MB來存儲呢？
如果使用10MB來存儲，位圖也搞不定了，這個時候就得使用分塊思想，用時間換空間，通過兩次遍歷來處理。
40億個數(shù)需要約500MB的空間，如果只有10MB的空間，至少需要50個塊才可以。一般劃分塊都使用2的冪次方的整數(shù)倍，此處劃分為64個塊是合理的。
首先將
0
?
2
32
0-2^{32}
0?232 這個范圍的數(shù)平均分成64個區(qū)間，每個區(qū)間是67 108 864個數(shù)，因為一共只有40億個數(shù)，所以在統(tǒng)計每一個區(qū)間上的數(shù)有多少時，肯定會有至少一個區(qū)間上的計數(shù)小于67 108 864。利用這一點可以找出其中一個沒出現(xiàn)過的數(shù)。具體過程如下：
第一次遍歷：先申請長度位64的整型數(shù)組countArr[0, ..., 63]，countArr[i]用來統(tǒng)計區(qū)間i上的數(shù)有多少。遍歷40億個數(shù)，跟去當(dāng)前數(shù)是多少來決定哪一個區(qū)間上的計數(shù)增加。比如，如果當(dāng)前數(shù)為2 567 278 189，2 567 278 189 / 67 108 864 = 38 ，所以第38個區(qū)間上計數(shù)增加countArr[51]++。遍歷完40億個數(shù)之后，遍歷countArr，必然會有某一個位置上的值（countArr[i]）小于67 108 864，表示第i區(qū)間上至少有一個數(shù)沒出現(xiàn)過。
此時使用的內(nèi)存是非常小的，是countArr的大?。?4 * 4B）
假設(shè)找到第37區(qū)間上的計數(shù)小于67 108 864，那么對這40億個數(shù)據(jù)進(jìn)行第二次遍歷：
- 申請長度為
67 108 864的位圖（bit map），占用大約8MB的空間，記為bitArr[0, ... , 67108863]。 - 遍歷這40億個數(shù)，此時的遍歷只關(guān)注落在第37區(qū)間上的數(shù)，記為
num(num滿足num / 67108864 = == 37)，其他區(qū)間的數(shù)全部忽略。 - 如果步驟2的
num在第37區(qū)間上，將bitArr[num - 67108864 * 37]的值設(shè)置為1，也就是只做第37區(qū)間上的數(shù)的bitArr映射。 - 遍歷完40億個數(shù)之后，在
bitArr上必然存在沒被設(shè)置成1的位置，假設(shè)第i個位置上的值沒被設(shè)置成1，那么67108864 * 37 + i這個數(shù)就是一個沒出現(xiàn)過的數(shù)
步驟小結(jié)：
- 根據(jù) 10MB 的內(nèi)存限制，確定統(tǒng)計區(qū)間的大小，就是第二次遍歷時的 bitArr 大小。
- 利用區(qū)間計數(shù)的方式，找到那個計數(shù)不足的區(qū)間，這個區(qū)間上肯定有沒出現(xiàn)的數(shù)。
- 對這個區(qū)間上的數(shù)做 bit map 映射，再遍歷bit map，找到一個沒出現(xiàn)的數(shù)即可。
1.3 如何確定分塊的區(qū)間
上面的例子中，采用兩次遍歷，第一次將數(shù)據(jù)分成64塊剛好解決問題，為什么不是128塊，32塊，16塊或者其他塊數(shù)呢？文章來源：http://www.zghlxwxcb.cn/news/detail-709227.html
這是主要為了保障第二次遍歷時每個塊都能放進(jìn)這10MB的空間中。 2 23 < 10 M B < 2 24 2^{23} < 10MB < 2^{24} 223<10MB<224，而 2 23 = 8388608 2^{23} = 8388608 223=8388608 大約是8MB，也就是說我們一次的分塊大小只能為8MB左右。我們在第二次遍歷時分成64塊剛好滿足要求，這是最少得分成64塊，當(dāng)然如果分成128塊、256塊也是可以的。文章來源地址http://www.zghlxwxcb.cn/news/detail-709227.html
到了這里，關(guān)于算法通關(guān)村第十五關(guān)——從40億個數(shù)中產(chǎn)生一個不存在的數(shù)的處理方法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
