題目：在一個(gè)文件中有 10G 個(gè)整數(shù)，亂序排列，要求找出中位數(shù)。內(nèi)存限制為 2G。只寫出思路即可（內(nèi)存限制為 2G的意思就是，可以使用2G的空間來(lái)運(yùn)行程序，而不考慮這臺(tái)機(jī)器上的其他軟件的占用內(nèi)存）。

關(guān)于中位數(shù)：數(shù)據(jù)排序后，位置在最中間的數(shù)值。即將數(shù)據(jù)分成兩部分，一部分大于該數(shù)值，一部分小于該數(shù)值。中位數(shù)的位置：當(dāng)樣本數(shù)為奇數(shù)時(shí)，中位數(shù)=(N+1)/2 ; 當(dāng)樣本數(shù)為偶數(shù)時(shí)，中位數(shù)為N/2與1+N/2的均值（那么10G個(gè)數(shù)的中位數(shù)，就第5G大的數(shù)與第5G+1大的數(shù)的均值了）。

分析：明顯是一道工程性很強(qiáng)的題目，和一般的查找中位數(shù)的題目有幾點(diǎn)不同。
1. 原數(shù)據(jù)不能讀進(jìn)內(nèi)存，不然可以用快速選擇，如果數(shù)的范圍合適的話還可以考慮桶排序或者計(jì)數(shù)排序，但這里假設(shè)是32位整數(shù)，仍有4G種取值，需要一個(gè)16G大小的數(shù)組來(lái)計(jì)數(shù)。

2. 若看成從N個(gè)數(shù)中找出第K大的數(shù)，如果K個(gè)數(shù)可以讀進(jìn)內(nèi)存，可以利用最小或最大堆，但這里K=N/2,有5G個(gè)數(shù)，仍然不能讀進(jìn)內(nèi)存。

3. 接上，對(duì)于N個(gè)數(shù)和K個(gè)數(shù)都不能一次讀進(jìn)內(nèi)存的情況，《編程之美》里給出一個(gè)方案：設(shè)k<K,且k個(gè)數(shù)可以完全讀進(jìn)內(nèi)存，那么先構(gòu)建k個(gè)數(shù)的堆，先找出第0到k大的數(shù)，再掃描一遍數(shù)組找出第k+1到2k的數(shù)，再掃描直到找出第K個(gè)數(shù)。雖然每次時(shí)間大約是nlog(k)，但需要掃描ceil(K/k) 次，這里要掃描5次。

解法：首先假設(shè)是32位無(wú)符號(hào)整數(shù)。
1. 讀一遍10G個(gè)整數(shù)，把整數(shù)映射到256M個(gè)區(qū)段中，用一個(gè)64位無(wú)符號(hào)整數(shù)給每個(gè)相應(yīng)區(qū)段記數(shù)。
說(shuō)明：整數(shù)范圍是0 - 2^32 - 1，一共有4G種取值，映射到256M個(gè)區(qū)段，則每個(gè)區(qū)段有16（4G/256M = 16）種值，每16個(gè)值算一段， 0～15是第1段，16～31是第2段，……2^32-16 ～2^32-1是第256M段。一個(gè)64位無(wú)符號(hào)整數(shù)最大值是0～8G-1，這里先不考慮溢出的情況。總共占用內(nèi)存256M×8B=2GB。

2. 從前到后對(duì)每一段的計(jì)數(shù)累加，當(dāng)累加的和超過(guò)5G時(shí)停止，找出這個(gè)區(qū)段（即累加停止時(shí)達(dá)到的區(qū)段，也是中位數(shù)所在的區(qū)段）的數(shù)值范圍，設(shè)為[a，a+15]，同時(shí)記錄累加到前一個(gè)區(qū)段的總數(shù)，設(shè)為m。然后，釋放除這個(gè)區(qū)段占用的內(nèi)存。

3. 再讀一遍10G個(gè)整數(shù)，把在[a，a+15]內(nèi)的每個(gè)值計(jì)數(shù)，即有16個(gè)計(jì)數(shù)。

4. 對(duì)新的計(jì)數(shù)依次累加，每次的和設(shè)為n，當(dāng)m+n的值超過(guò)5G時(shí)停止，此時(shí)的這個(gè)計(jì)數(shù)所對(duì)應(yīng)的數(shù)就是中位數(shù)。

總結(jié)：
1.以上方法只要讀兩遍整數(shù)，對(duì)每個(gè)整數(shù)也只是常數(shù)時(shí)間的操作，總體來(lái)說(shuō)是線性時(shí)間。

2. 考慮其他情況。
若是有符號(hào)的整數(shù)，只需改變映射即可。若是64為整數(shù)，則增加每個(gè)區(qū)段的范圍，那么在第二次讀數(shù)時(shí)，要考慮更多的計(jì)數(shù)。若過(guò)某個(gè)計(jì)數(shù)溢出，那么可認(rèn)定所在的區(qū)段或代表整數(shù)為所求，這里只需做好相應(yīng)的處理。噢，忘了還要找第5G+1大的數(shù)了，相信有了以上的成果，找到這個(gè)數(shù)也不難了吧。

3. 時(shí)空權(quán)衡。
花費(fèi)256個(gè)區(qū)段也許只是恰好配合2GB的內(nèi)存（其實(shí)也不是，呵呵）。可以增大區(qū)段范圍，減少區(qū)段數(shù)目，節(jié)省一些內(nèi)存，雖然增加第二部分的對(duì)單個(gè)數(shù)值的計(jì)數(shù)，但第一部分對(duì)每個(gè)區(qū)段的計(jì)數(shù)加快了（總體改變？？待測(cè)）。

4. 映射時(shí)盡量用位操作，由于每個(gè)區(qū)段的起點(diǎn)都是2的整數(shù)冪，映射起來(lái)也很方便。

原文地址 http://www.cppblog.com/richbirdandy/