---
title: "347. Top K Frequent Elements"
url: "https://laigary.com/interview/coding/347-top-k-frequent-elements"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-26"
tags: ["Heap", "Hash Table", "Classic"]
---

# 347. Top K Frequent Elements

[347\. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/)

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

## 思路

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

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

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

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

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

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

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

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

**Python 只有最小堆**，要模擬最大堆就把值取負再放進去，見 [Python 面試技巧](/interview/coding/python-tips-for-interview)。

## 解題方向

### 全部丟進最大堆，彈 k 次

```python
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 的最小堆

```python
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 放進堆，最後直接取堆裡的東西：

```python
        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](/interview/coding/215-kth-largest-element-in-an-array)、[703. Kth Largest Element in a Stream](/interview/coding/703-kth-largest-element-in-a-stream)（資料流版，同一個大小 k 的堆）、[973. K Closest Points to Origin](/interview/coding/973-k-closest-points-to-origin)、[295. Find Median from Data Stream](/interview/coding/295-find-median-from-data-stream)（雙堆）、[692. Top K Frequent Words](/interview/coding/692-top-k-frequent-words)（多一個字典序的 tie-break）。整理見 [Heap / Top K 模板](/interview/coding/heap-topk-template)。

## 複雜度

設 `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` 時第二種明顯較快。