347. Top K Frequent Elements

──────────────────────────────────────────────────────────────────────

回傳出現頻率前 k 高的元素。

思路

題目拆成兩步，各自都很單純：

算出每個元素的頻率 → Counter(nums)， $O (n)$
從這些頻率裡挑出前 k 大 → 這才是考點

第 2 步就是標準的 Top-K 問題。看到「前 k 個 / 第 k 大 / 資料流中動態取最值」就要想到 heap，這是 Heap / Top K 模板的核心訊號。

大小為 k 的最小堆，還是全部丟進去？

兩種都可行，差別在複雜度：

做法	時間	適合什麼場合
全部 `m` 個丟進堆，再彈 k 次	$O (m \log m)$	寫起來最直覺
只維持大小 k 的最小堆	$O (m \log k)$	`k` 遠小於 `m` 時明顯更快

第二種的關鍵手法是：用最小堆存「目前的前 k 名」。堆頂是這 k 個裡最小的，新來的元素只要比堆頂大就把堆頂擠掉。這樣堆永遠只有 k 個元素。

聽起來反直覺（要前 k 大卻用最小堆），但正是因為堆頂是「門檻」—— 要淘汰的永遠是最弱的那個，所以要讓最弱的浮在頂端方便取出。這個「求最大用最小堆」的顛倒是 Top-K 題的標誌性技巧。

Python 只有最小堆，要模擬最大堆就把值取負再放進去，見 Python 面試技巧。

解題方向

全部丟進最大堆，彈 k 次

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:

        counter = Counter(nums)

        pq = []

        heapq.heapify(pq)

        for key in counter.keys():
            heapq.heappush(pq, (-counter[key], key))

        res = []

        while k > 0:
            value, key = heapq.heappop(pq)
            res.append(key)
            k -= 1

        return res

(-counter[key], key) 用負的頻率當排序鍵，於是最小堆彈出的就是頻率最大的。push tuple 是 heapq 的標準用法：它會按第一個元素排序，相同時比第二個。

heapq.heapify(pq) 在這裡是多餘的（pq 還是空的），可以省掉。

這版最好想，缺點是堆裡放了全部 m 個相異元素。

只維持大小 k 的最小堆

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:        
        counter = Counter(nums)
        
        vals = list(counter.values())
        
        heap = []
        for val in vals:
            heapq.heappush(heap, val)
            if len(heap) > k:
                heapq.heappop(heap)
    
        kFreq = heap[0]
    
        res = []
        for key, val in counter.items():
            if val >= kFreq:
                res.append(key)
        
        return res

先用大小 k 的最小堆求出「第 k 大的頻率」kFreq，再掃一遍把所有頻率 >= kFreq 的元素收集起來。

這個寫法依賴題目那句「答案唯一」的保證。 如果第 k 名和第 k+1 名的頻率相同，最後那一輪會把兩個都收進去，回傳超過 k 個元素。例如 nums = [1,2,3], k = 2：三個數字的頻率都是 1，kFreq 是 1，於是回傳 [1, 2, 3] —— 三個。LeetCode 這題保證答案唯一所以不會踩到，但換成沒有這個保證的題目就會錯。

比較穩健的做法是把 (頻率, 元素) 整個 tuple 放進堆，最後直接取堆裡的東西：

        heap = []
        for key, val in counter.items():
            heapq.heappush(heap, (val, key))
            if len(heap) > k:
                heapq.heappop(heap)
        return [key for val, key in heap]

這樣堆裡永遠正好 k 個，不需要事後再掃一遍，也不會被平手影響。

補充

還有 $O (n)$ 的解法：桶排序。 頻率的範圍一定在 1 到 n 之間，所以可以開 n+1 個桶，把元素依頻率丟進對應的桶，再從高頻往低頻收集 k 個。不需要排序也不需要堆。我沒有用這個角度寫過這題，但知道「頻率有上界 → 可以用桶」這條線值得記著，面試被追問「能不能不用 $O (\log k)$ 」時就是這個答案。

同一組 Top-K 工具的題目：215. Kth Largest Element in an Array、703. Kth Largest Element in a Stream（資料流版，同一個大小 k 的堆）、973. K Closest Points to Origin、295. Find Median from Data Stream（雙堆）、692. Top K Frequent Words（多一個字典序的 tie-break）。整理見 Heap / Top K 模板。

複雜度

設 n 是陣列長度、m 是相異元素個數（m ≤ n）。

全部丟進堆

時間 $O (n + m \log m)$ — 計數 $O (n)$ ，建堆與彈出 $O (m \log m)$
空間 $O (m)$ — counter 加上堆

大小 k 的最小堆

時間 $O (n + m \log k)$ — 每次 push/pop 只花 $O (\log k)$
空間 $O (m)$ — counter 佔 $O (m)$ ，堆只佔 $O (k)$

桶排序

時間 $O (n)$
空間 $O (n)$

k 遠小於 m 時第二種明顯較快。