（給算法愛好者加星標，修煉編程內功）
作者：蒼痕
blog.csdn.net/wangbaochu/article/details/52949443
【前言】 找一個無序數組裡面的第 K 大數，你有什麼好方法嗎？ 本文介紹了五種可行的方案，希望能對大家有所啟發，如果你有什麼更好的方法，也歡迎你留言，大家一起討論。
經典問題：寫一段程序，找出數組中第k大的數，輸出數所在的位置。
我們先假設元素的數量不大，例如在幾千個左右，在這種情況下，那我們就排序一下吧。
在這裡，快速排序或堆排序都是不錯的選擇，他們的平均時間複雜度 都是 O（N * logN）。
然後取出前 K 個，O（K）。總時間複雜度 O（N * logN）+ O（K） = O（N * logN）。
你一定注意到了，當 K=1 時，上面的算法也是 O（N * logN）的複雜度，而顯然我們可以通過 N-1 次的比較和交換得到結果。
上面的算法把整個數組都進行了排序，而原題目只要求最大的 K 個數，並不需要前 K 個數有序，也不需要後 N-K 個數有序。
怎麼能夠避免做後 N-K 個數的排序呢？我們需要部分排序的算法，選擇排序和交換排序都是不錯的選擇。
把 N 個數中的前 K 大個數排序出來，複雜度是O（N * K）。
那一個更好呢？O（N * logN）還是 O（N * K）？這取決於 K 的大小，這是你需要在面試者那裡弄清楚的問題。在 K（K < = logN）較小的情況下，可以選擇部分排序。
【解法二】改進的快速排序方法：避免對所有的數排序，利用快速排序分堆，然後遞歸另外一半（不需要兩半都遞歸），直到最終所有小於基準數的個數為K回憶一下快速排序，快排中的每一步，都是將待排數據分做兩組，其中一組的數據的任何一個數都比另一組中的任何一個大，然後再對兩組分別做類似的操作，然後繼續下去……
在本問題中，假設 N 個數存儲在數組 S 中，我們從數組 S 中隨機找出一個元素 X，把數組分為兩部分 Sa 和 Sb。Sa 中的元素大於等於 X，Sb 中元素小於 X。
這時，有兩種可能性：
1. Sa中元素的個數小於K，Sa中所有的數和Sb中最大的K-|Sa|個元素（|Sa|指Sa中元素的個數）就是數組S中最大的K個數。
2. Sa中元素的個數大於或等於K，則需要返回Sa中最大的K個元素。
這樣遞歸下去，不斷把問題分解成更小的問題，平均時間複雜度 O（N *logK）。
（1）按數值區間二分搜索
對於一個給定的數 p，可以在 O（N）的時間複雜度內找出所有不小於 p 的數。假如 N 個數中最大的數為 Vmax，最小的數為 Vmin，那麼這 N 個數中的第 K 大數一定在區間[Vmin, Vmax]之間。那麼，可以在這個區間內二分搜索 N 個數中的第 K大數 p。偽代碼如下：
while (Vmax-Vmin > delta){ Vmid = Vmin + (Vmax – Vmin) * 0.5; if(f(arr, N, Vmid) >= K) Vmin = Vmid; else Vmax = Vmid;}偽代碼中 f（arr, N, Vmid）返回數組 arr[0, …, N-1]中大於等於 Vmid 的數的個數。
上述偽代碼中，delta 的取值要比所有 N 個數中的任意兩個不相等的元素差值之最小值小。如果所有元素都是整數，delta 可以取值 0.5。
循環運行之後，最終得到一個很小的區間（Vmin, Vmax），這個區間僅包含一個元素（或者多個相等的元素），則這個元素就是第 K 大的元素。
整個算法的時間複雜度為 O（N * log2（|Vmax – Vmin|/delta））。
由於 delta 的取值要比所有 N 個數中的任意兩個不相等的元素差值之最小值小，因此時間複雜度跟數據分布相關。在數據分布平均的情況下，時間複雜度為 O（N * log2（N））。
（2）從另一個角度: 按比特位二分搜索
假設所有整數的大小都在[0, 2^m-1]之間，也就是說所有整數在二進位中都可以用 m bit 來表示（從低位到高位,分別用 0, 1, …, m-1 標記）。
我們可以先考察在二進位位的第（m-1）位，將 N 個整數按該位為 1 或者 0 分成兩個部分。也就是將整數分成取值為[0, 2m-1-1]和[2m-1, 2m-1]兩個區間。
前一個區間中的整數第（m-1）位為 0，後一個區間中的整數第（m-1）位為 1。
如果該位為 1 的整數個數 A 大於等於 K，那麼，在所有該位為 1 的整數中繼續尋找最大的 K 個。否則，在該位為 0 的整數中尋找最大的 K-A 個。
接著考慮二進位位第（m-2）位，以此類推。思路跟上面的區間中值數的情況本質上一樣。
對於上面兩個方法，我們都需要遍歷一遍整個集合，統計在該集合中大於等於某一個數的整數有多少個。
不需要做隨機訪問操作，如果全部數據不能載入內 存，可以每次都遍歷一遍文件。經過統計，更新解所在的區間之後，再遍歷一次文件，把在新的區間中的元素存入新的文件。下一次操作的時候，不再需要遍歷全部 的元素。
每次需要兩次文件遍歷，最壞情況下，總共需要遍歷文件的次數為2 * log2（|Vmax – Vmin|/delta）。由於每次更新解所在區間之後，元素數目會減少。
當所有元素能夠全部載入內存之後，就可以不再通過讀寫文件的方式來操作了。
【解法四】堆排序法：非常適合內存有限，數據海量的情況。我們已經得到了三個解法，不過這三個解法有個共同的地方，就是需要對數據訪問多次，那麼就有下一個問題，如果 N 很大呢，100 億？（更多的情況下，是面試者問你這個問題）。
這個時候數據不能全部裝入內存（不過也很難說，說知道以後會不會 1T 內存比 1 斤白菜還便宜），所以要求儘可能少的遍歷所有數據。
不妨設 N > K，前 K 個數中的最大 K 個數是一個退化的情況，所有 K 個數就是最大的 K 個數。
如果考慮第 K+1 個數 X 呢？如果 X 比最大的 K 個數中的最小的數 Y 小，那麼最大的 K 個數還是保持不變。
如果 X 比 Y 大，那麼最大的 K個數應該去掉 Y，而包含 X。
如果用一個數組來存儲最大的 K 個數，每新加入一個數 X，就掃描一遍數組，得到數組中最小的數 Y。
用 X 替代 Y，或者保持原數組不變。這樣的方法，所耗費的時間為 O（N * K）。
進一步，可以用容量為 K 的最小堆來存儲最大的 K 個數。
最小堆的堆頂元素就是最大 K 個數中最小的一個。每次新考慮一個數 X，如果 X 比堆頂的元素Y 小，則不需要改變原來的堆，因為這個元素比最大的 K 個數小。
如果 X 比堆頂元素大，那麼用 X 替換堆頂的元素 Y。
在 X 替換堆頂元素 Y 之後，X 可能破壞最小堆的結構（每個結點都比它的父親結點大），需要更新堆來維持堆的性質。更新過程花費的時間複雜度為 O（log2K）。
因此，算法只需要掃描所有的數據一次，時間複雜度為 O（N * log2K）。這實際上是部分執行了堆排序的算法。
在空間方面，由於這個算法只掃描所有的數據一次，因此我們只需要存儲一個容量為 K 的堆。
大多數情況下，堆可以全部載入內存。如果 K 仍然很大，我們可以嘗試先找最大的 K』個元素，然後找第 K』+1個到第 2 * K』個元素，如此類推（其中容量 K』的堆可以完全載入內存）。不過這樣，我們需要掃描所有數據 ceil1（K/K』）次。
【解法五】鍵值索引法：適用於數據的取值範圍不太大的情景，可以將每個數作為輔助數組的索引，計算每個數出現的次數。統計所有的次數，找到第K個數。能否有確定的線性算法呢？是否可以通過改進計數排序、基數排序等來得到一個更高效的算法呢？答案是肯定的。但算法的適用範圍會受到一定的限制。
如果所有 N 個數都是正整數，且它們的取值範圍不太大，可以考慮申請空間，記錄每個整數出現的次數，然後再從大到小取最大的 K 個。
比如，所有整數都在（0, MAXN）區間中的話，利用一個數組 count[MAXN]來記錄每個整數出現的個數（count[i]表示整數 i 在所有整數中出現的個數）。
我們只需要掃描一遍就可以得到 count 數組。然後，尋找第 K 大的元素：
for (sumCount = 0, v = MAXN-1; v >= 0; v–-){ sumCount += count[v]; if(sumCount >= K) break;}return v;- EOF -
覺得本文有幫助？請分享給更多人
推薦關注「算法愛好者」，修煉編程內功
點讚和在看就是最大的支持❤️