本文轉載自微信公眾號「Kirito的技術分享」，作者kiritomoe。轉載本文請聯系Kirito的技術分享公眾號。

簡單抽象一下問題，便是今天的主題：在一個百萬級無序的 long 數組中，尋找第 K 大的數。要求當然是越快找到越好。

top K 問題

題面一描述出來，很多人都會聯想到 top K 問題，這道題無論是算法領域還是工程領域，都討論的極其廣泛，并且在實際項目中也很容易會遇到類似的問題，我也正好趁著這個機會總結成一篇文章。

常見的 top K 問題，及其變種：

1. 有 10000000 個記錄，這些查詢串的重復度比較高，如果除去重復后，不超過 3000000 個。一個查詢串的重復度越高，說明查詢它的用戶越多，也就是越熱門。請統計最熱門的 10 個查詢串，要求使用的內存不能超過 1GB。
2. 有 10 個文件，每個文件 1GB，每個文件的每一行存放的都是用戶的 query，每個文件的 query 都可能重復。按照 query 的頻度排序。
3. 有一個 1GB 大小的文件，里面的每一行是一個詞，詞的大小不超過 16 個字節，內存限制大小是 1MB。返回頻數最高的 100 個詞。
4. 提取某日訪問網站次數最多的那個 IP。
5. 10 億個整數找出重復次數最多的 100 個整數。
6. 搜索的輸入信息是一個字符串，統計 300 萬條輸入信息中最熱門的前 10 條，每次輸入的一個字符串為不超過 255B，內存使用只有 1GB。
7. 有 1000 萬個身份證號以及他們對應的數據，身份證號可能重復，找出出現次數最多的身份證號。

傳統 top K 問題的描述：

在海量數據中找出最大的前 K 個數

注意我這次提出的問題和傳統 top K 有一點區別，傳統的 top K 問題要求的一般是”前 K 大的數“，而我現在遇到的是”第 K 大的數“。區別要說大也不大，但對于我們最終選擇的方案可能會有很大的區別。

我下面會介紹一些傳統的 top K 問題的解決思路。并且，按照我一貫的風格，肯定會有代碼放出來，你如果是為了尋找一個”海量無序數據尋找第 K 大的數“問題的答案，相信你可以直接 copy 我的代碼。

方案一：排序法

排序法是最容易想到的思路，復雜度為 O(nlogn) 。能夠想到的各類排序算法呼之欲出，快速排序、歸并排序、插入排序、猴子排序...etc

但是工程領域選擇方案，往往不能僅僅使用算法復雜度來評估：

• 每個排序方案數據的交換量
• 額外空間的申請量
• 平均復雜度
• 最壞復雜度
• 不同數據量下的表現

那這個時候有人就要問了，我該如何選擇合適的方案呢?哎，那我又要提到那句話了，benchmark everything!雖然你肯定知道我最終沒有選擇使用排序來解決第 K 大的問題，但我還是想分享給你我的一些測試結論。

在 100w~1000w 數據量級別的無序 long 數組中，JDK 自帶的 Array.sort() 比任何一個排序方案都要快。

Array.sort 的內部實現為 timsort，是一種優化過后的歸并排序。

排序單純靠想也知道不是最優的方案，因為我提出的問題中，僅僅需要找到第 K 大的數，排序方案卻興師動眾把整個數組理順了，沒必要。

方案二：堆

針對一般的 top K 問題，一般都會默認 K 很小，所以一般的 top K 問題，可以選擇使用堆來解決。

堆有個重要的性質：每個結點的值均不大于其左右孩子結點的值，則堆頂元素即為整個堆的最小值。JDK 中 PriorityQueue 實現了堆這個數據結構堆，通過指定 comparator 字段來表示小頂堆或大頂堆，默認為自然序(natural ordering)。

小頂堆解決 Top K 問題的思路：小頂堆維護當前掃描到的最大 K 個數，其后每一次掃描到的元素，若大于堆頂則入堆，然后刪除堆頂;依此往復，直至掃描完所有元素。Java 實現第 K 大整數代碼如下：

public int findKthLargest(int[] nums, int k) { 
  PriorityQueue<Integer> minQueue = new PriorityQueue<>(k); 
  for (int num : nums) { 
    if (minQueue.size() < k || num > minQueue.peek()) 
      minQueue.offer(num); 
    if (minQueue.size() > k) 
      minQueue.poll(); 
  } 
  return minQueue.peek(); 
} 

回到我遇到的問題，求第 K 大的數，這里沒有說明 K 的范圍，那么最壞情況下，K == N/2，無論維護一個 top K 的小頂堆還是維護一個 top(N - K) 的大頂堆，都需要占用 O(N/2) 的內存，而對于海量數據而言，這顯示是一筆非常大的開銷。所以針對我比賽的場景，堆的方案可以直接 pass。

堆的解法適用于 K 較小的場景，而且非常方便維護前 K 個數。

方案三：Quick Select

Quick Select 你可能沒聽過，但快速排序(Quick Sort)你肯定有所耳聞，其實他們兩個算法的作者都是 Hoare，并且思想也非常接近：選取一個基準元素 pivot，將數組切分(partition)為兩個子數組，比 pivot 大的扔左子數組，比 pivot 小的扔右子數組，然后遞推地切分子數組。Quick Select 不同于 Quick Sort 之處在于其沒有對每個子數組做切分，而是對目標子數組做切分。其次，Quick Select 與Quick Sort 一樣，是一個不穩定的算法;pivot 選取直接影響了算法的好壞，最壞情況下的時間復雜度達到了 O(n2)。

在大學參加 ACM 時，我便第一次接觸了該算法，記得那時數據量正好卡的 Quick Sort 無法通過，Quick Select 可以通過。

Quick Select 的 Java 實現如下：

public static long quickSelect(long[] nums, int start, int end, int k) { 
        if (start == end) { 
            return nums[start]; 
        } 
        int left = start; 
        int right = end; 
        long pivot = nums[(start + end) / 2]; 
        while (left <= right) { 
            while (left <= right && nums[left] > pivot) { 
                left++; 
            } 
            while (left <= right && nums[right] < pivot) { 
                right--; 
            } 
            if (left <= right) { 
                long temp = nums[left]; 
                nums[left] = nums[right]; 
                nums[right] = temp; 
                left++; 
                right--; 
            } 
        } 
        if (start + k - 1 <= right) { 
            return quickSelect(nums, start, right, k); 
        } 
        if (start + k - 1 >= left) { 
            return quickSelect(nums, left, end, k - (left - start)); 
        } 
        return nums[right + 1]; 

最終，我選擇使用了方案三：Quick Select 作為我求解第 K 大數的方案，也是 benchmark 下來最快的方案。在 10 次查詢中，排序方案耗時為 6s，而 Quick Select 方案，僅需要 300ms，可以說是非常大的優化。

總結

本文簡單介紹了無序數組求 Top K 問題和無序數組求第 K 大數字兩類非常相似的問題，并且提供了常見的三種解決方案。當然，該問題也有很多變種，例如在多核機器，多主機上求解 TopK，甚至可以引入外排和 MapReduce 的思想，其實已經是在考慮其他層面的優化了，我在這里就不過多闡釋了。