這是我在面試騰訊時遇到的真實面試題，在很多面經(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 進(jìn)行 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]; // 省略了隨機(jī)選擇元素的過程
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的差值，補(bǔ)相應(yīng)的p就好了。例子：
S = [1, 2, 3, 3, 5]，p = 3，K = 2；即我們知道第K大的數(shù)p為 3，我們遍歷一遍 S，把所有大于p的數(shù)取出來，即[5]，接下來補(bǔ)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ù)在二進(jìn)制中都可以用
m bit來表示(從低位到高位，分別用0, 1, ..., m-1標(biāo)記)。我們可以先考察在二進(jìn)制位的第(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個。接著考慮二進(jìn)制位第(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ù)。
回憶我們的堆排序，我們需要維護(hù)一個最大堆/最小堆，關(guān)鍵點就在這里了。我們可以從100億個數(shù)據(jù)中取出前K個，然后用這K個數(shù)建立一個最小堆，之后去遍歷所有數(shù)據(jù)，每取出一個數(shù)，如果大于當(dāng)前堆中的最小值，就替換掉當(dāng)前的最小堆中的最小值，然后維護(hù)堆的秩序，只需遍歷所有數(shù)據(jù)一次，我們就能獲得有序的最大 K 個數(shù)。維護(hù)堆的時間復(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,需要進(jìn)行的更新操作偽代碼如下:
解讀下偽代碼，一開始進(jìn)行判斷X是否大于當(dāng)前的堆里面最小值，如果比這個堆的最小值還小，那就不用看了，肯定不是最大的K個數(shù)之一；如果是大于最小值，那么就替換掉最小值，如下圖所示：
然后我們就要維護(hù)堆的秩序了，依次將X跟它的左右孩子進(jìn)行比較，如果比它們大，就要交換，否則不動，假設(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ù)量，且可更新，有序 |
參考書籍：《編程之美》
