347. 前 K 个高频元素

题目链接（中等）

题目描述

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

数据范围：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度 必须优于 O(n log n)，其中 n 是数组大小。

示例

示例 1：

输入： nums = [1,1,1,2,2,3], k = 2
输出： [1,2]

示例 2：

输入： nums = [1], k = 1
输出： [1]

示例 3：

输入： nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出： [1,2]

核心思路

两步走：

1. 统计频率：用哈希表记录每个元素出现的次数；
2. 取前 k 大：从「频率数组」里选出频率最高的 k 个元素。

第 1 步一定是 $O(n)$，关键在于第 2 步的效率。

三种主流做法：

1. 小根堆：维护大小为 k 的最小堆，堆顶是当前 k 个中的最小频率，$O(n \log k)$；
2. 快速选择：类似 LC 215，对「元素-频率」数组做 partition，平均 $O(n)$；
3. 桶排序：频率最高不超过 n，用桶按频率分组，从高往低取，$O(n)$。

---

方法一：小根堆（$O(n \log k)$）

思路及解法

关键观察：要找频率最高的 k 个元素，可以用大小为 k 的小根堆维护。

流程：

1. 用哈希表统计每个元素的频率；
2. 遍历频率表，把 (num, freq) 依次加入小根堆：
   • 堆大小 < k：直接入堆；
   • 堆大小 = k：比较当前元素频率和堆顶频率，若当前元素频率更大，弹出堆顶并加入当前元素；
3. 遍历结束后，堆中剩下的就是频率前 k 高的元素。

为什么用小根堆？

堆里始终保留「当前频率最高的 k 个元素」。小根堆的堆顶是这 k 个里频率最小的，用来快速淘汰：「新元素频率比堆顶还小，就不可能是前 k，直接跳过；否则替换掉堆顶」。

对偶思维：如果求「前 k 小」，就用大根堆，逻辑完全对称。

代码

import heapq
from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        # 统计频率
        count = Counter(nums)

        # 小根堆，按频率比较
        heap = []
        for num, freq in count.items():
            if len(heap) < k:
                heapq.heappush(heap, (freq, num))
            elif freq > heap[0][0]:
                heapq.heapreplace(heap, (freq, num))

        # 堆中元素就是前 k 高频
        return [num for _, num in heap]

注意：堆里存 (freq, num) 而不是 (num, freq)，因为 heapq 默认按元组第一个元素比较。这样堆顶就是频率最小的元素。

复杂度分析

• 时间复杂度：$O(n \log k)$，统计频率 $O(n)$，遍历频率表 $O(n \log k)$（每次堆操作 $O(\log k)$）。
• 空间复杂度：$O(n)$，哈希表存最多 n 个元素，堆大小为 k。

---

方法二：快速选择（平均 $O(n)$）

思路及解法

思路：把问题转成「在频率数组中找前 k 大的元素」，和 LC 215 完全一样。

步骤：

1. 用哈希表统计频率，转成列表 items = [(num, freq)]；
2. 对 items 做快速选择：类似快排 partition，但每次只递归一侧；
3. 找到分界点，使得左侧 k 个是频率最高的 k 个；
4. 返回这 k 个元素的 num。

快速选择的核心：

• 选一个主元 pivot（这里用频率）；
• 把「频率 ≥ pivot」的放到左边，「< pivot」的放到右边；
• 分界点 index 左边的就是频率较高的部分：
  • 若 k <= index - start，答案全在左半部分，递归左半；
  • 否则左半部分全部保留，再去右半找剩余的。

代码

import random
from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        count = Counter(nums)
        items = list(count.items())   # [(num, freq), ...]
        result = []

        def quickselect(start: int, end: int, k: int) -> None:
            if start > end:
                return

            # 随机选主元，避免最坏情况
            picked = random.randint(start, end)
            items[start], items[picked] = items[picked], items[start]

            pivot_freq = items[start][1]
            index = start
            # 频率 ≥ pivot 的放左边
            for i in range(start + 1, end + 1):
                if items[i][1] >= pivot_freq:
                    index += 1
                    items[index], items[i] = items[i], items[index]
            items[start], items[index] = items[index], items[start]

            left_count = index - start       # 左侧（含 pivot）共 left_count + 1 个
            if k <= left_count:
                quickselect(start, index - 1, k)
            else:
                # 左侧全部收下
                for i in range(start, index + 1):
                    result.append(items[i][0])
                if k > left_count + 1:
                    quickselect(index + 1, end, k - (left_count + 1))

        quickselect(0, len(items) - 1, k)
        return result

复杂度分析

• 时间复杂度：平均 $O(n)$，最坏 $O(n^2)$（可用随机主元降低概率）。
• 空间复杂度：$O(n)$，哈希表 + items 列表 + 递归栈。

---

方法三：桶排序（$O(n)$，最优）

思路及解法

关键观察：元素的频率最多是 n（所有元素相同）。所以可以用「频率」作为桶的下标，把相同频率的元素放到同一个桶里。

流程：

1. 用哈希表统计每个元素的频率；
2. 创建 n + 1 个桶，bucket[f] 存放所有频率为 f 的元素；
3. 从高频率桶往低频率桶遍历，依次把元素加入答案，直到收集够 k 个。

为什么是 $O(n)$？

• 统计频率 $O(n)$；
• 放桶 $O(n)$；
• 从高到低遍历桶，最多遍历 n 个桶，每个桶最多遍历所有元素一次，$O(n)$；
• 总时间 $O(n)$。

代码

from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        count = Counter(nums)
        n = len(nums)

        # bucket[f] 存放所有频率为 f 的元素
        bucket = [[] for _ in range(n + 1)]
        for num, freq in count.items():
            bucket[freq].append(num)

        result = []
        # 从高频率往低频率遍历
        for f in range(n, 0, -1):
            for num in bucket[f]:
                result.append(num)
                if len(result) == k:
                    return result

        return result

复杂度分析

• 时间复杂度：$O(n)$，三次线性遍历。
• 空间复杂度：$O(n)$，哈希表 + 桶 + 结果数组。

---

三种方法对比

方法	时间	空间	特点
小根堆	$O(n \log k)$	$O(n)$	模板通用，Top K 问题的标准解法
快速选择	平均 $O(n)$	$O(n)$	效率高，但代码较长
桶排序	$O(n)$	$O(n)$	时间最优，代码短，依赖频率有界

推荐：

• 面试：首选 小根堆，模板通用，容易讲清；
• 进阶：如果面试官要求「优于 $O(n \log n)$」，可以写桶排序，代码最短且是 $O(n)$；
• 想展示技巧：快速选择 与 LC 215 一脉相承，可以提一句「和找第 K 大元素是同一套思路」。

---

关键细节

1. 为什么堆里存 (freq, num) 而不是 (num, freq)

Python 的 heapq 默认按元组第一个元素比较。我们要堆按频率排序，所以把 freq 放在第一个位置：

heapq.heappush(heap, (freq, num))   # 堆顶是 freq 最小的

如果写反了，堆会按 num 排序，达不到「小根堆维护频率最小」的效果。

2. 为什么堆的大小固定为 k

因为题目只要求前 k 高频，堆的大小超出 k 就浪费空间，也无法快速淘汰。堆大小恰好是 k 时，堆顶就是「当前前 k 高频中最不频的那个」，方便淘汰。

3. 桶排序的频率上界

桶的大小是 n + 1，因为频率最大为 n（所有元素都是同一个值）。bucket[f] 用列表存储，因为可能有多个元素的频率相同。

4. 为什么桶排序不用排序

桶的下标本身就是「频率」，从 n 遍历到 1 就是天然从高到低的顺序，不需要任何排序操作。

5. 三者的选择标准

场景	推荐
通用 Top K 问题	小根堆
求第 K 大 / 前 K 大（不需要有序）	快速选择
数据范围明确、频率有界	桶排序

---

与 LC 215 的对比

	LC 215 第 K 大	LC 347 前 K 高频
求什么	单个元素	k 个元素
核心步骤	partition	统计频率 + partition
快速选择	只递归一侧	只递归一侧 + 左侧全保留
堆方法	大根堆删 k-1 次 / 小根堆维护 k 个	小根堆维护 k 个
特殊方法	—	桶排序

共同点：都是 Top K 问题，可以用小根堆或快速选择解决。LC 347 多了「统计频率」这一步。

---

总结

• 通用套路：Top K 问题三件套——排序、堆、快速选择；
• 小根堆：
  • 维护大小为 k 的最小堆，堆顶是「当前 k 个中最小频率」；
  • 遍历时若新元素频率更大，替换堆顶；
  • 时间 $O(n \log k)$，空间 $O(n)$；
• 快速选择：
  • 对「(元素, 频率)」数组做 partition；
  • 只递归一侧，平均 $O(n)$；
• 桶排序：
  • 用频率作桶的下标；
  • 从高到低遍历桶，收集 k 个元素；
  • 时间 $O(n)$，空间 $O(n)$；
• 记忆口诀：「Top K 用小根堆，求第 K 大用快速选择，频率有界用桶排序」。

相关题目

• LC 215. 数组中的第 K 个最大元素（快速选择）
• LC 692. 前 K 个高频单词（本题 + 排序规则）
• LC 451. 根据字符出现频率排序（哈希 + 排序）
• LC 973. 最接近原点的 K 个点（快速选择 / 堆）
• LC 剑指 Offer 40. 最小的 k 个数（快速选择）