题目链接#

LeetCode 347. 前K个高频元素

题目描述#

给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。 你可以按任意顺序返回答案。

解法：Counter + 小顶堆#

这题最经典、也最顺手的写法，就是：

• 先用 Counter 统计每个元素出现的次数
• 再用一个大小不超过 k 的小顶堆，维护当前前 k 个高频元素

1
import heapq
2
from collections import Counter
3

4
class Solution(object):
5
    def topKFrequent(self, nums, k):
6
        """
7
        :type nums: List[int]
8
        :type k: int
9
        :rtype: List[int]
10
        """
11
        counter = Counter(nums)
12
        heap = []
13

14
        for item, freq in counter.items():
15
            heapq.heappush(heap, (freq, item))
16
            if len(heap) > k:
17
                heapq.heappop(heap)
18

19
        return [item for freq, item in heap]

第一步：先统计频率#

这一步很直白：

1
counter = Counter(nums)

比如：

1
nums = [1, 1, 1, 2, 2, 3]

统计结果就是：

1
{1: 3, 2: 2, 3: 1}

意思是：

• 1 出现了 3 次
• 2 出现了 2 次
• 3 出现了 1 次

既然题目比较的是“谁更高频”，那就必须先把这个频率表做出来。

第二步：为什么用小顶堆#

堆里存的不是单独的元素，而是：

1
(频率, 元素值)

比如：

1
(3, 1)
2
(2, 2)
3
(1, 3)

因为 Python 的 heapq 默认是小顶堆，所以堆顶永远是当前堆里频率最小的那个。

这正好适合这题。 因为我们想维护的是：

当前频率最高的前 k 个元素

所以每来一个新元素：

• 先把它压入堆
• 如果堆的大小超过了 k
• 就把堆顶弹出去

被弹出去的，就是当前前 k 名里最不够格的那个。

为什么这样做一定对#

因为整个过程中，堆始终只保留“目前见过的前 k 高频元素”。

• 如果一个新元素频率更高，它就会把低频元素挤掉
• 如果一个新元素频率不够高，它即使先进堆，也会很快被弹出去

等遍历结束后，堆里剩下的自然就是出现频率最高的前 k 个元素。

结合样例走一遍#

比如：

1
nums = [1, 1, 1, 2, 2, 3]
2
k = 2

先统计频率：

1
counter = {
2
    1: 3,
3
    2: 2,
4
    3: 1
5
}

然后依次入堆。

1
heap = [(3, 1)]

1
heap = [(2, 2), (3, 1)]

1
heap = [(1, 3), (3, 1), (2, 2)]

1
heapq.heappop(heap)

1
(1, 3)

1
[(2, 2), (3, 1)]

1
[2, 1]

复杂度分析#

假设数组长度为 n，不同元素个数为 m。

1
O(n + m log k)

1
O(n log k)

1
O(m)

这题和 215 的区别#

这题和 LeetCode 215《数组中的第 K 个最大元素》很像，都是用堆维护“前 K 名”。

但两题维护的东西不一样：

1
元素值本身

1
(频率, 元素)

补充：为什么不用直接排序频率表#

当然也可以先统计频率，再把所有元素按频率排序。

比如：

1
counter = Counter(nums)
2
sorted_items = sorted(counter.items(), key=lambda x: x[1], reverse=True)
3
return [item for item, freq in sorted_items[:k]]

这样也能做出来。

但它的时间复杂度通常是：

1
O(m log m)

相比之下，小顶堆只需要维护 k 个元素，效率会更好，尤其是当 k 远小于不同元素个数 m 时，更有优势。

小结#

这题真正的主线很清楚：

1. 先统计频率
2. 再用小顶堆维护前 k 个高频元素
3. 堆满了就弹出频率最小的那个

如果只记一句话，那我建议记这个：

先数人头，再留前 K 名。

这题不难，重点就是把“统计”和“维护前 K 名”这两步拆开想清楚。 想通了之后，代码就会写得很顺。🦐