這是我在面試騰訊時遇到的真實面試題，在很多面經(jīng)中也能看到它的身影汁果，今天我們就來徹底地搞懂它驾中！
問題描述
如何從 10w 的數(shù)據(jù)中找到最大的 100 個數(shù)？
首先看問題分衫，10w 的數(shù)據(jù)场刑，在堆上建個數(shù)組暴力求是沒有問題的，要找最大的 100 個數(shù)丐箩，那么先從最簡單最暴力的方法開始摇邦。
1. 排序法
眾所周知，快速排序和堆排序的時間復(fù)雜度都可以達(dá)到 屎勘，我們只要給 10w 數(shù)據(jù)排個序施籍，然后取出前 100 個就好了。這種方法很暴力概漱，在數(shù)據(jù)總數(shù)不是很大時確實可以使用丑慎，比如100個里面取前20個；當(dāng)然，面試時我們只需簡單地提一下這種解法竿裂，就可以說下一種優(yōu)化方法了玉吁。至于排序，不是本文的重點腻异。
接下來考慮優(yōu)化进副，我們只需要前 100 個，為什么要把全部數(shù)據(jù)排序呢悔常？
2. 局部排序法
我們回憶一下冒泡排序和選擇排序的過程影斑，在前 k 次循環(huán)中，可以得出前 k 個最大/最小值机打。
以冒泡排序（降序）為例：
for(int i = 0; i < n; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] < arr[j+1])
swap(arr, j, j+1); // 交換 arr[j] 和 arr[j+1]
}
}
因此在這里矫户，我們正好利用這兩種排序算法的特性，簡單寫下代碼：
// 我們只需要把最外層的 n 換為 k
for(int i = 0; i < k; i++) {
for (int j = 0; j < n-i-1; j++) {
//...
}
}
這樣子残邀，就能獲得最大的前 k 個數(shù)皆辽，并且位于 arr 中的前 k 個位置，這樣的時間復(fù)雜度就變?yōu)榱?芥挣。
簡單比較下前兩種方法的時間復(fù)雜度：
和
驱闷，到低哪個好，得根據(jù) K 和 N 的大小來看九秀，如果 K 較幸潘浴（K <=
） 的情況下，我們可以采用局部排序法鼓蜒。
3. Partition
回憶一下快速排序痹换，快排中的每一步，都是將待排數(shù)據(jù)分做兩組都弹，其中一組的數(shù)據(jù)的任何一個數(shù)都比另一組中的任何一個大娇豫，然后再對兩組分別做類似的操作，然后繼續(xù)下去...
如下圖畅厢，將 arr 中的數(shù)據(jù)分為小于 k和大于k兩部分：
接下來冯痢，我們來看怎么利用這種思想求出最大的K個數(shù)。
我們假設(shè)存在一個數(shù)組S框杜，從中隨意挑出了一個數(shù) X浦楣，然后將數(shù)組 S 分為兩部分：
- A：大于等于X
- B：小于X
如下圖所示，我們對數(shù)組 S 進行 Partition 操作咪辱，可以得到兩種情況：
-
如果
A的個數(shù)大于K振劳，那么數(shù)組S的最大K個數(shù)，就是A中的最大K個數(shù)油狂；這個很好理解历恐，相當(dāng)于說
年級（S）前十名（K）一定是年級前五十名（A）中的前十名（K） -
如果
A的個數(shù)小于K寸癌，我們就需要在B中找到剩余的部分，也就是A+B中的K-|A|個弱贼；同樣的蒸苇，
年級（S）前十名（K）一定是年級前三名（A）加上年級4-100名（B）中的前7名（K-|A|）；
如果上面這部分還沒理解吮旅，可以參考下方這個小例子溪烤，如果理解了，跳過即可：
我們只需重復(fù)上面的操作庇勃，遞歸直到找到前K個數(shù)即可氛什， 這樣的平均時間復(fù)雜度為 。
這里附一份偽代碼：
我根據(jù)這份偽代碼簡單寫了下代碼：（Java實現(xiàn)匪凉，但以通用方式來寫，對于cpp捺檬、go都有參考價值）
建議大家一定要自己動手實現(xiàn)再层，光看代碼是不夠的，萬一面試官讓你手寫代碼你就傻眼了堡纬。另外聂受，這份代碼為了好理解，很多地方實際上是不規(guī)范的烤镐，比如變量名用大寫字母等等蛋济，這些大家在寫的時候是可以想辦法去優(yōu)化的。
public int[] KBig(int[] S, int K) {
if (K <= 0) {
return new int[0];
}
if (S.length <= K) {
return S;
}
Sclass sclass = Partition(S);
return contact(KBig(sclass.Sa, K), KBig(sclass.Sb, K - sclass.Sa.length));
}
public Sclass Partition(int[] S) {
Sclass sclass = new Sclass();
int p = S[0]; // 省略了隨機選擇元素的過程
for (int i = 1; i < S.length; i++) {
if (S[i] > p) {
sclass.Sa = append(sclass.Sa, S[i]);
} else {
sclass.Sb = append(sclass.Sb, S[i]);
}
}
if (sclass.Sa.length < sclass.Sb.length) {
sclass.Sa = append(sclass.Sa, p);
} else {
sclass.Sb = append(sclass.Sb, p);
}
return sclass;
}
注意到偽代碼中返回了兩個數(shù)組炮叶，我們這里用一個類來存這兩個數(shù)組：
class Sclass { // 單純用來存儲兩個數(shù)組
int[] Sa = new int[0];
int[] Sb = new int[0];
}
輔助函數(shù)：
/**
* 在數(shù)組 arr 的末尾插入值 value
* @param arr 數(shù)組
* @param value 值
* @return 返回插入后的數(shù)組
*/
int[] append(int[] arr, int value) {
int[] res = new int[arr.length + 1];
System.arraycopy(arr, 0, res, 0, arr.length);
res[arr.length] = value;
return res;
}
/**
* 將兩個數(shù)組連接到一起
* @param a 數(shù)組a
* @param b 數(shù)組b
* @return 返回連接后的數(shù)組
*/
public int[] contact(int[] a, int[] b) {
int[] res = new int[a.length + b.length];
for (int i = 0; i < a.length; i++) { // 通用的拷貝方式
res[i] = a[i];
}
// 在 java 中實際上可以通過 System.arraycopy 完成拷貝
System.arraycopy(b, 0, res, a.length, b.length);
return res;
}
當(dāng)你寫完代碼碗旅，測試一下就會發(fā)現(xiàn)，實際上這種方法返回的最大的K個數(shù)是沒有排序的（其實題目也沒有要求你排序镜悉，且如果你對Partition的過程很清楚的話祟辟， 你也很容易知道這里返回的是無序的最大K個數(shù)）我們需要考慮清楚應(yīng)用場景，有些場景沒有排序要求侣肄，有些場景有旧困，要學(xué)會選擇。
4. 二分搜索
我們要找數(shù)組S中最大的K個數(shù)稼锅，那么如果我們知道了第K大的數(shù)吼具，事情會變得簡單嗎？聰明的讀者可能已經(jīng)發(fā)現(xiàn)了矩距，如果我們知道了數(shù)組S中第K大的數(shù)p拗盒，那么我們只需遍歷一遍數(shù)組，就能找到最大的K個數(shù)剩晴。（即所有大于等于p的數(shù)）锣咒，這一步的時間復(fù)雜度為 侵状。
有讀者可能會問，如果等于
p的值有多個毅整，這樣遍歷一遍取出來的數(shù)多于K個趣兄，怎么辦呢？事實上解決的辦法有很多悼嫉，我這里簡單說一種艇潭，遍歷的時候只把大于
p的數(shù)取出來，最后根據(jù)大于p的數(shù)和K的差值戏蔑，補相應(yīng)的p就好了蹋凝。例子：
S = [1, 2, 3, 3, 5]，p = 3总棵，K = 2鳍寂；即我們知道第K大的數(shù)p為 3，我們遍歷一遍 S情龄，把所有大于p的數(shù)取出來迄汛，即[5]，接下來補K- [5].size() = 1個p骤视，即[5,3]就是最大的 K 個數(shù)鞍爱。
回到我們的二分搜索方法中來，我們需要在S中找到第K大的數(shù)专酗，偽代碼如下：
- Vmax：數(shù)組S中的最大值
- Vmin：數(shù)組S中的最小值
- delta：比
所有N個數(shù)中的任意兩個不相等的元素差值的最小值小睹逃。如果所有元素都是整數(shù), delta可以取值0.5。
整個算法的時間復(fù)雜度為 祷肯。
在數(shù)據(jù)平均分布的情況下沉填，時間復(fù)雜度為 。
在整數(shù)的情況下佑笋，可以從另一個角度來看這個算法拜轨。假設(shè)所有整數(shù)的大小都在
之間，也就是說所有整數(shù)在二進制中都可以用
m bit來表示(從低位到高位允青，分別用0, 1, ..., m-1標(biāo)記)橄碾。我們可以先考察在二進制位的第(m-1)位，將N個整數(shù)按該位為1或者0分成兩個部分颠锉。也就是將整數(shù)分成取值為和
兩個區(qū)間法牲。
前一個區(qū)間中的整數(shù)第(m-1)位為0，后一個區(qū)間中的整數(shù)第(m-1)位為1琼掠。如果該位為1的整數(shù)個數(shù)A大于等于K拒垃，那么,在所有該位為1的整數(shù)中繼續(xù)尋找最大的K個。否則瓷蛙，在該位為0的整數(shù)中尋找最大的K-A個悼瓮。接著考慮二進制位第(m-2)位戈毒，以此類推。思路跟上面的浮點數(shù)的情況本質(zhì)上一樣横堡。
5. BFPRT算法
這個算法比較復(fù)雜埋市，我們這里不做詳細(xì)介紹，簡單說下命贴， 也是類似快速排序的思想道宅，但是能從n個元素的序列中選出第k大/小的元素，且保證最壞時間復(fù)雜度為 胸蛛。
為什么
的算法不講污茵，要去講那些看起來更 “慢” 的算法呢？要注意葬项，我們通常講的時間復(fù)雜度是
平均/最差泞当，而且是忽略掉系數(shù)的，真實應(yīng)用場景下還要考慮是否容易實現(xiàn)（過于復(fù)雜的可能頻繁出bug得不償失）民珍，還要考慮各種各樣的問題零蓉，并不是無腦選擇時間復(fù)雜度低的方法。
這個方法配合我們前面所說的穷缤，已知數(shù)組S中第K大的數(shù)p，我們只需再遍歷一遍數(shù)組箩兽，就能找到最大的K個數(shù)津肛。這一步的時間復(fù)雜度也為 。
所以總的時間復(fù)雜度就是 汗贫。
算法步驟：
將n個元素每5個一組身坐，分成
n/5(上界)組。取出每一組的中位數(shù)落包，任意排序方法部蛇，比如插入排序。
遞歸的調(diào)用
selection算法查找上一步中所有中位數(shù)的中位數(shù)咐蝇，設(shè)為x涯鲁，偶數(shù)個中位數(shù)的情況下設(shè)定為選取中間小的一個。用
x來分割數(shù)組有序，設(shè)小于等于x的個數(shù)為k抹腿，大于x的個數(shù)即為n-k。若
i==k旭寿，返回x警绩；若i!=k，在大于x的元素中遞歸查找第i-k小的元素盅称。終止條件：n=1時肩祥，返回的即是i小元素后室。
6. 最大最小堆
我們前面談到的解法有個共同的地方，如果數(shù)據(jù)量較大時混狠，就得對數(shù)據(jù)訪問多次岸霹。
那么如果面試官問的不是從 10w 中找100個數(shù)，而是10億呢? 這個時候數(shù)據(jù)是不能一次性讀入內(nèi)存的檀蹋，所以我們要盡可能少的遍歷所有數(shù)據(jù)松申。
回憶我們的堆排序，我們需要維護一個最大堆/最小堆俯逾，關(guān)鍵點就在這里了贸桶。我們可以從100億個數(shù)據(jù)中取出前K個，然后用這K個數(shù)建立一個最小堆桌肴，之后去遍歷所有數(shù)據(jù)皇筛，每取出一個數(shù)，如果大于當(dāng)前堆中的最小值坠七，就替換掉當(dāng)前的最小堆中的最小值水醋，然后維護堆的秩序，只需遍歷所有數(shù)據(jù)一次彪置，我們就能獲得有序的最大 K 個數(shù)拄踪。維護堆的時間復(fù)雜度為 ，所以算法總體的時間復(fù)雜度為
拳魁。
啰嗦一句惶桐，我們這里是用最小堆，去存最大的
k個數(shù)潘懊，為什么不用最大堆來存呢姚糊？因為更新的時候又得調(diào)換下順序，沒有必要多此一舉授舟。
接下來我們詳細(xì)說說算法該怎么實現(xiàn)救恨，對堆排序熟悉的同學(xué)可能已經(jīng)可以自己寫出來了，那么可以跳過這部分释树。
我們使用一個數(shù)組H[]來建立一個K=8的堆：
我們知道肠槽，堆中的每個元素H[i]，它的父親結(jié)點是H[i/2]奢啥，左孩子結(jié)點是H[2*i+ 1]署浩，右孩子結(jié)點是H[2*i+2]。每新考慮一個數(shù)X,需要進行的更新操作偽代碼如下:
解讀下偽代碼扫尺，一開始進行判斷X是否大于當(dāng)前的堆里面最小值筋栋，如果比這個堆的最小值還小，那就不用看了正驻，肯定不是最大的K個數(shù)之一弊攘；如果是大于最小值抢腐，那么就替換掉最小值，如下圖所示：
然后我們就要維護堆的秩序了襟交，依次將X跟它的左右孩子進行比較迈倍，如果比它們大，就要交換捣域，否則不動啼染，假設(shè)X大于H[1]，那么X就要跟H[1]交換：
交換完后焕梅，p=q迹鹅，所以接下來會繼續(xù)判斷X和H[3]的大小，假設(shè)X小于H[3]贞言，那么就X就停止于此斜棚，結(jié)束循環(huán)。
7. 總結(jié)
| 方法 | 時間復(fù)雜度 | 特點 |
|---|---|---|
| 排序法 | 實現(xiàn)簡單该窗，數(shù)據(jù)量小弟蚀，對速度要求不敏感 | |
| 局部排序法 | 實現(xiàn)簡單，數(shù)據(jù)量小酗失，且對速度不敏感時义钉，<br /> |
|
| Partition | 速度快，返回數(shù)據(jù)無序 | |
| 二分搜索 | 速度較快规肴，特定場景下可以使用位來實現(xiàn) | |
| BFPRT | 實際效果并沒有想象中的好 | |
| 最大最小堆 | 支持超大數(shù)據(jù)量捶闸，且可更新，有序 |
參考書籍：《編程之美》
