資源限制類問題的常用解決方案
說明
以下提到的數據結構和元素類型均基於Java語言。
問題1
32位無符號整數的範圍是
0~4,294,967,295(即：0 ~ 2^32 - 1）現在有一個正好包含40億個無符號整數的文件，可以使用最多1GB的內存，怎麼找到出現次數最多的數？
首先，需要考慮最差情況，假設40億個數都不一樣。
如果使用Hash表，key表示其中的某個數，value表示出現的次數，由於
40億 > Integer.MAX_VALUE
所以Hash表的key和value都需要long類型來存，
Hash表中的每條記錄至少需要
8Byte + 8Byte = 16Byte
最差情況，40億條不同記錄進入Hash表，
需要
16Byte * 40億 = 640億Byte
約等於64G。內存不夠。
如果申請數組來存，由於Java中數組長度有限制(Integer.MAX_VALUE)，所以要存下40億個數，一個數組一定不夠。
long類型的多個數組假設把所有40億個不同的數都存下，
需要的內存空間是：
40億 * 8Byte = 320億Byte
約等於32G, 內存也不夠。
如果只有1G內存，如果用Hash表，key和value均為long類型，即一條記錄大約8Byte，保守估計，可以裝下
1G / 8 Byte = 10億Byte / 8Byte = 1.25億，
在這個1.25億基礎上再減少到1千萬， 處理1千萬種類的數據，絕對不會超過現有的內存限制。通過如下計算
40億 / 1千萬 = 400
我們可以創建400個空文件，然後，對於每一個數m，通過hash函數得到一個hash值，假設m的哈希值為n, 然後用n
hash(m) % 400 = n % 400 = i
得到的i的值是多少，就把m這個值分配到第i號文件中。
根據hash函數的性質，相同的數一定進入同一個文件。 且400個文件中每個文件大約都是1千萬種數。
使用hash表統計每個文件中出現次數最多的數（最多1千萬種左右，hash表在現有資源限制下無壓力），就是整個文件出現次數最多的數。
問題2
32位無符號整數的範圍是
0~4,294,967,295，現在有一個正好包含40億個無符號整數的文件，所以在整個範圍中必然存在沒出現過的數, 可以使用最多1GB的內存，怎麼找到所有未出現過的數？
如果使用HashSet，需要用long類型來存，大約需要
40億 * 8Byte = 320億Byte
大約32G，內存不夠。
我們可以使用bit數組(位圖)來存每個數是否出現，0表示出現，1表示沒有出現。Java中，一個int類型可以表示32位， 因為要標識每個數是否出現過。所以2^32個數大約需要
(2^32) / 8 = 537M
537M空間的內存佔用，滿足限制條件。
Java中，因為每個int數字可以表示32位的二進制數，所以可以使用int數組來構造位圖,
參考如下示例代碼(179這個數字是否出現過)：
int[] arr = new int[10];
int i = 179;
int status = (arr[i / 32] & (i << (i % 32 ))) == 0 ? 0 : 1
status = 0則表示沒有出現過，status = 1則表示沒有出現過。
問題3
32位無符號整數的範圍是
0~4,294,967,295，現在有一個正好包含40億個無符號整數的文件，所以在整個範圍中必然存在沒出現過的數, 內存限制為3KB，只用找到一個沒出現過的數即可。
3KB 如果用來表示long類型的數組，數組最大長度大約是
3KB / 8Byte = 375。大約375長度, 然後我們尋找比375小的離375最近的2的某次方的數，得到256, 那我們可以申請一個256長度的long類型數組，假設叫arr。
由於數字一共有2^32次方個，我們可以將
2^32 / 256 = 16,777,216
均分成256份，每一份負責統計每16,777,216個數出現的次數。
arr[0] 統計 0 ~ 16,777,215出現的次數。
arr[1] 統計 16,777,216 ~ （16,777,216 + 16,777,215） 出現的次數。
…..
arr[255] 統計 （2^32 - 1 - 16,777,215） ~ 2^32 - 1 出現過的數。
由於現在的數個數是40億, 不到2^32次方，所以，肯定有某個位置上的arr值不夠16,777,216個。 由於只需要找到一個沒有出現過的數，所以只需要在不夠16,777,216這個範圍的位置上進行再一次的256份的劃分，然後再次使用上述邏輯，直到劃分到某個數單獨作為一個範圍同時沒出現過，這個數就是我們需要找的數。
問題4
32位無符號整數的範圍是
0~4,294,967,295，現在有一個正好包含40億個無符號整數的文件，所以在整個範圍中必然存在沒出現過的數, 只能使用有限幾個變量，如何找到一個沒出現過的數（找到一個即可）。
參考問題3，我們可以設置一個變量L定位第0個數，設置變量R定位2^32-1上的數，設置M變量定位到中間位置。由於一共有2^32次方個數，所以統計左邊和右邊都應該有2^31個數，但是總共40億個數，所以必然有一邊不滿足2^31方個數，然後不滿足的這一邊繼續二分，重複上述邏輯，即可找到沒有出現過的一個數字。
問題3和問題4類似，我們可以得到一個結論： 如果內存3KB，就用256分，如果是幾個變量，就用二分。
問題5
有一個包含100億個URL的大文件，假設每個URL佔用64B，請找出其中所有重複的URL。
如果允許失誤率，這個問題可以使用布隆過濾器來解決。
如果不允許失誤，則可以使用問題1的方法，Hash函數結合取模操作，分到小文件思想。
問題6
32位無符號整數的範圍是
0~4294967295，現在有40億個無符號整數，可以使用最多1GB的內存，找出所有出現了兩次的數。
問題2中，我們拿一個bit來表示一個數出現過一次或者沒出現過，本問題我們可以拿兩個bit來表達一個數出現的次數。
00表示沒出現
01表示出現過1次
10表示出現過2次
11表示出現過3次及3次以上
問題7
32位無符號整數的範圍是
0~4294967295，現在有40億個無符號整數, 可以使用最多3KB的內存，怎麼找到這40億個整數的中位數？
參考問題3的做法，把整個2^32個數均分到一個256長度的long型數組中，每個位置管理16,777,216個數出現的次數。 然後逐個累加區間中數字出現的次數，一直累加到21億左右，即可判斷，中位數一定存在這個區間中。
問題8
32位無符號整數的範圍是
0~4294967295，有一個10G大小的文件，每一行都裝着這種類型的數字，整個文件是無序的，給你5G的內存空間，請你輸出一個10G大小的文件，就是原文件所有數字排序的結果。
我們定義一個數據結構
class Node {
long value;
long times;
}
value表示文件中的數值，times表示文件中的數值出現的次數。
然後設置一個大根堆存Node。value大的數值在堆頂， 假設堆大小我們設置為3，每次遍歷的數和次數加入大根堆。大根堆滿了以後，如果新加入一個大根堆中沒有的數，則比較新加入的數和大根堆堆頂元素，如果比堆頂元素小，則剔除堆頂元素，加入新元素。遍歷一輪以後，大根堆中的三個數一定是整個文件中最小的三個數。然後把這三個數和次數依次寫入新文件，然後繼續上述遍歷和處理。每次都可以拿到三個排序後的數值，直接加入到新文件即可。
所以，因為本問題中有5G內存，根據我們上述的方案，綽綽有餘。
問題9
某搜索公司一天的用戶搜索詞彙是海量的(百億數據量)，請設計一種求出每天熱門Top100詞彙的可行辦法。
參考問題1，我們可以使用Hash函數結合取模操作，分到小文件思想。
然後使用大根堆，統計每個文件中的top100。
最後，把每個文件對應的大根堆的堆頂元素彈出放入新的一個大根堆（假設這個大根堆叫superHeap）中。然後從這個新的大根堆的堆頂彈出堆頂元素，即為全局top1。
然後看這個彈出的堆頂元素是來自於哪個文件，繼續把這個文件對應的大根堆堆頂元素彈出，繼續放入superHeap中，然後從superHeap彈出堆頂元素，就是全局top2。
…..
依次類推，直到top100。
