Top-K Problems前 K 大

01為什麼需要它

看到這些關鍵字就想到它：前 K 大／小、第 K 大、最常出現的 K 個、離某點最近的 K 個、K 遠小於 n、資料是串流。

02核心概念

要找前 K 大，直覺是全部排序取前 K 個，O(n log n)。但你只需要 K 個，其餘 n − K 個的順序完全不重要。大小為 K 的最小堆積只記住目前最好的 K 個，而且堆頂是這 K 個裡最小的，也就是「入榜門檻」：新元素比門檻小就不用理它，比門檻大就把門檻踢掉換它進來。每個元素最多一次 O(log K) 的操作，整體 O(n log K)。

方向很容易搞反：找前 K 大用最小堆積，找前 K 小用最大堆積。記法是「堆頂是最容易被淘汰的那個」。同一個堆積掃完後，堆頂就是第 K 大，所以「第 K 大」和「前 K 大」是同一題。

還有兩條路。Quick Select：用快速排序的分割一次砍掉一半，平均 O(n)，但需要整份資料在記憶體、也不適合串流。桶排序：當要比的是「出現次數」時，次數最多是 n，開 n 個桶把元素按次數丟進去，從大的桶往回收，O(n)。選哪個看 K 的大小、資料是否為串流、以及要比的值有沒有範圍限制。

03演算法步驟

1. 1確認目標：前 K 大用最小堆積，前 K 小用最大堆積。若要比的是次數或距離，先算出那個值，堆積裡放 (值, 元素) 的 tuple。
2. 2逐個掃過元素。堆積還沒滿 K 個就直接 push。
3. 3滿了之後，新元素和堆頂比較：不比堆頂好就跳過（O(1)），比堆頂好就 pop 堆頂再 push 它（Python 用 heapreplace 一次做完）。
4. 4掃完後堆積裡就是答案。要有序輸出就逐個 pop 再反轉；只要第 K 大就直接看堆頂。
5. 5若 K 接近 n、資料不是串流、只跑一次，改用 Quick Select 或直接排序可能更快；要比的是次數時考慮桶排序。

04互動示範

K = 3。逐筆掃過閱讀數，堆頂（黃色）是入榜門檻。留意有多少筆連堆積都不用碰，直接被跳過。

05程式碼

前 K 大、第 K 大、出現次數前 K 高三種變形，加上桶排序的 O(n) 版本作對照。C++ 另外示範 nth_element，那就是標準庫的 Quick Select。

import heapq
from collections import Counter


def top_k_largest(nums, k):
    """前 K 大：維持一個大小為 K 的最小堆積。O(n log k)"""
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:                # 比門檻大才有資格進榜
            heapq.heapreplace(heap, x)   # pop 最小再 push，一次 O(log k)
    return sorted(heap, reverse=True)


def kth_largest(nums, k):
    """第 K 大：同樣的堆積，最後堆頂就是答案"""
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]


def top_k_frequent(words, k):
    """出現次數前 K 高：先計數，再對 (次數, 字) 做 Top-K"""
    count = Counter(words)
    # nlargest 內部就是大小為 k 的堆積
    return heapq.nlargest(k, count, key=count.get)


def top_k_frequent_bucket(nums, k):
    """次數的範圍最多是 n，可以用桶排序做到 O(n)"""
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for x, c in count.items():
        buckets[c].append(x)
    out = []
    for c in range(len(buckets) - 1, 0, -1):
        out.extend(buckets[c])
        if len(out) >= k:
            return out[:k]
    return out

06練習題

• LeetCode 215Kth Largest Element in an Array（堆積與 Quick Select 各做一次）Medium
• LeetCode 347Top K Frequent Elements（試試桶排序版）Medium
• LeetCode 973K Closest Points to OriginMedium
• LeetCode 692Top K Frequent Words（次數相同時按字典序）Medium
• LeetCode 1985Find the Kth Largest Integer in the Array（字串比較）Medium