企业官网建设流程全解析

LeetCode 347这道题，我面试里遇到过不止一次，身边朋友被问到的概率也极高。它表面只要求“统计频率 + 取前K个”，但真正考察的是你对哈希表、堆、桶排序、快速选择这些基础数据结构的理解深度，以及面试时能不能把复杂度讲明白。这篇文章我按自己的刷题经验，把四种主流解法从思路到代码再到坑点，完整拆一遍。

1. 题目拆解与核心思路

1.1 题目到底在问什么

给你一个整数数组nums和一个整数k，要求返回出现频率前k高的元素。比如输入nums = [1,1,1,2,2,3], k = 2，输出就是[1,2]，因为1出现3次、2出现2次、3只出现1次。答案不要求按频率排序，所以[2,1]也算正确。

这题有个隐藏前提：题目保证答案唯一，不用处理频率并列的复杂情况。实际面试中最好主动确认一句“如果频率相同，返回哪个都可以吗”，这个小动作能让面试官觉得你考虑问题周全。

1.2 为什么这道题是面试高频题

因为它在“中等难度”里卡得恰到好处。暴力解法一眼就能想到，但面试官会一步步追问“能不能优化”“还有没有别的方法”，从排序到堆、从桶排序到快速选择，每层优化都在考察不同的知识模块。一道题能串起哈希表、优先队列、分治思想、复杂度分析四大块，性价比极高。

而且这题在很多真实业务场景中都有投影：比如从日志里统计 Top 10 错误码、从搜索记录里提取热门关键词、从用户行为中挖掘高频访问页面。算法题背后就是这些实实在在的需求，面试官问它一点都不奇怪。

2. 暴力解法与基础优化

2.1 哈希表 + 全排序的思路

最直觉的做法是两步走：先用哈希表统计每个数字的出现次数，再把所有键值对按次数从大到小排序，取前k个。

def topKFrequent(nums, k): count = {} for num in nums: count[num] = count.get(num, 0) + 1 sorted_pairs = sorted(count.items(), key=lambda x: x[1], reverse=True) return [pair[0] for pair in sorted_pairs[:k]]

这段代码能过题目测试，但时间复杂度是O(n log n)，空间复杂度O(n)。问题在于：我们只需要前k个最大值，却把整个数组排了序，n log n的排序成本里很大一部分是浪费的。

从业务角度理解：假如要统计一亿条日志里的 Top 10 错误码，为这 10 个结果把一亿条数据全部排序，代价明显不合理。

2.2 复杂度瓶颈在哪里

瓶颈不在哈希统计，这一步O(n)是必须花的时间，瓶颈在排序。只要涉及全量排序，复杂度下限就是O(n log n)。面试官听到你给出这个答案后，下一句几乎一定是“能不能做到比O(n log n)更好”，标准的追问路径。

此时思路要转一个弯：维护一个大小为k的容器，让容器里始终只保留当前的前k高频元素，用“局部有序”替代“全局有序”，复杂度就有机会降到O(n log k)甚至O(n)。

3. 最优解法一：哈希表 + 小顶堆

3.1 为什么是小顶堆而不是大顶堆

这是面试中最常推的解法，也是最推荐的写法。核心思想是：维护一个大小为k的小顶堆，遍历哈希表时，如果堆里元素不足k个就直接放入；如果堆已满，当前元素的频率比堆顶大，就弹出堆顶、把当前元素放进去。

为什么用小顶堆？因为我们要留住“最大的 k 个”，小顶堆的堆顶是堆里最小的那个。新元素只要比“前 k 名里最弱的那一个”强，就有资格进堆，把最弱的挤出去。反过来，如果用大顶堆，堆顶是最大的，你没法判断新元素该不该进堆，因为你要挤掉的是最小的，而大顶堆看不到最小元素。

生活类比：小顶堆就像一个只招 k 个人的排行榜，排在末位的人是“守门员”，新选手只有打败守门员才能上位。

3.2 完整代码实现

import heapq def topKFrequent(nums, k): count = {} for num in nums: count[num] = count.get(num, 0) + 1 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)) return [pair[1] for pair in heap]

这段代码有几个细节值得展开：

第一，堆里存的是(freq, num)二元组。Python 的heapq在比较元组时优先比较第一个元素，所以必须把频率放在前面。如果写成(num, freq)，堆排序会按哈希表的键排序，结果完全错误。

第二，heapreplace等价于先heappop再heappush，但效率更高，因为它只需要一次上下调整，而pop + push需要两次调整。虽然常数因子差异不大，但面试时能说出这种细节，会显得你写过不少真实代码。

第三，如果freq == heap[0][0]，即频率跟堆顶一样大，我选择不替换。因为题目保证答案唯一，并列情况不需要处理，保持堆内元素不变即可。这个边界判断很重要，很多人写代码时漏掉“等于”的情况，导致堆中出现重复元素。

3.3 时间复杂度的准确计算

这段代码的时间复杂度是O(n log k)，而不是O(n log n)，关键在于堆的大小被限制在k。每次堆操作的成本是O(log k)，最多处理n个不同的数字（实际是哈希表里不重复元素的数量），所以总成本O(n log k)。当k远小于n时，这个优势非常明显。

空间复杂度是O(n)，主要由哈希表贡献，堆本身只占O(k)额外空间。面试中如果要抠得更细，可以补充一句：如果只看堆的部分，空间是O(k)，但整体算法必须统计所有元素频率，所以哈希表的O(n)是不可避免的。

3.4 堆解法适合什么场景

堆解法适合k比较小、数据流式的场景。真实系统中经常用“固定大小的堆”来处理流式数据：数据源源不断进来，堆始终只保留 Top k，不需要把所有历史数据存下来。如果面试官追问“如果数据无限流入怎么办”，堆解法就是标准答案的雏形。

另外，heapq是 Python 内置模块，不需要额外依赖，刷题和工程化场景都能直接用。这也是我优先推荐堆解法的原因之一。

4. 最优解法二：桶排序思路

4.1 桶排序怎么解决这个问题

如果频率分布相对集中，也就是数组中不同元素数量不多，可以用桶排序把时间复杂度优化到O(n)。思路是：创建n + 1个桶，下标i的桶里放“出现次数正好为 i 的所有元素”。最后从后往前遍历桶，依次取出元素，直到取满k个。

def topKFrequent(nums, k): count = {} for num in nums: count[num] = count.get(num, 0) + 1 buckets = [[] for _ in range(len(nums) + 1)] for num, freq in count.items(): buckets[freq].append(num) result = [] for freq in range(len(buckets) - 1, 0, -1): for num in buckets[freq]: result.append(num) if len(result) == k: return result

这段代码的时间复杂度：统计O(n)，建桶O(n)，遍历桶最坏情况下O(n)，合计O(n)。空间复杂度O(n)。

4.2 桶排序的适用边界与代价

桶排序的代价是要分配一个长度为n + 1的数组，不管实际上有多少个不同频率，都会占用这么多空间。如果n = 10，这个开销无所谓；如果n = 1000万，仅桶数组就是 1000 万个列表对象，内存消耗可能比堆解法大一个数量级。

所以桶排序适用于“频率分布集中”的场景。极端情况下，比如数组里只有一两个不同元素，桶会非常稀疏，此时内存浪费严重。但如果面试中你主动提到“这个解法有额外内存开销，适合普通数据量”，同时对比堆解法的优劣，会显得你对工程细节有把控力。

4.3 桶下标的细节对照

桶排序的陷阱在于索引对齐：频率最低是 1，最高是n，所以需要n + 1个桶。如果某个数字出现n次，正好放进下标为n的桶，不会越界。很多人在面试时写buckets = [[] for _ in range(n)]，频率为n的元素会导致IndexError，这属于一次性 bug，写了就能看出来，但现场紧张时容易漏。

逆向遍历时要注意：频率高的元素优先被收集，返回结果天然就是“按频率从高到低排列”的。虽然题目不要求排序，但拿到一个有序结果总归是加分项。我刷题时习惯了从后往前遍历写，避免遗漏。

5. 最优解法三：快速选择算法

5.1 快速选择的核心思想

快速选择是基于快速排序的分区思想：每轮选定一个基准，把数组分成“基准左边 <= 基准”和“基准右边 > 基准”两部分。如果基准恰好落在n - k位置，说明基准及它右边的元素就是前k大的，直接返回即可；如果落在左边，说明前k大还在右边，继续递归右半部分；反之递归左半部分。

这题的“元素列表”是哈希表里的所有键值对，比较依据是频率值。因此不能用原数组的数值直接比较，而要先做一次频率统计，再在(num, freq)列表上做分区。

import random def topKFrequent(nums, k): count = {} for num in nums: count[num] = count.get(num, 0) + 1 items = list(count.items()) # [(num, freq), ...] n = len(items) target = n - k def partition(left, right): pivot_index = random.randint(left, right) pivot_freq = items[pivot_index][1] items[pivot_index], items[right] = items[right], items[pivot_index] store = left for i in range(left, right): if items[i][1] < pivot_freq: items[store], items[i] = items[i], items[store] store += 1 items[right], items[store] = items[store], items[right] return store left, right = 0, n - 1 while True: pos = partition(left, right) if pos == target: return [item[0] for item in items[pos:]] elif pos < target: left = pos + 1 else: right = pos - 1

5.2 随机化的重要性

划重点：快速选择一定要加随机化。如果不加随机，每次选基准都用固定位置（比如最右边），当数据接近有序时，分区极度不平衡，复杂度退化成O(n²)。加了随机化之后，期望时间复杂度是O(n)，这是一个数学期望值，不是最坏情况保证。

为什么期望是O(n)？因为每次分区期望把问题规模缩小一半左右，代价从n降到n/2再降到n/4……加起来是n + n/2 + n/4 + ... = 2n，所以期望是O(n)。听起来很划算，但要注意这是“期望”，如果运气不好连续选到最差基准，还是会退化。实际编码时用random.randint即可。

5.3 快速选择的优缺点对比

最大优点是平均线性时间，面试官听到你能说出“平均O(n)”通常会眼前一亮。缺点是常数因子偏大（随机数生成、多次交换），而且代码比堆解法复杂不少，现场写容易在 partition 边界上翻车。

我的建议是：如果面试中时间充裕、思路清晰，可以展示快速选择来体现功力；如果想稳扎稳打，堆解法是更安全的选择。两种都写熟练，面试时根据题目难度和现场状态灵活选用。

6. 面试沟通与常见坑点总结

6.1 面试官最想听到的思维链路

最理想的答题流程是：先给出暴力解法，明确说出它的复杂度；然后自己指出“全量排序做了无用功”，引出堆解法；写完堆解法后，主动补充“如果数据量小、内存充足，还有桶排序的线性解法”；最后可以提一句快速选择作为理论最优解。每一步都有清晰的时间复杂度演进：O(n log n) → O(n log k) → O(n)，这种递进式回答在面试中非常加分。

我见过很多候选人一上来就写堆，虽然是对的，但面试官无法判断你是真的理解还是背了模板。从暴力解法开始讲，反而是展示思考能力的信号。

6.2 Python heap 的常见陷阱

heapq默认为小顶堆，没有直接的大顶堆参数。如果题目想取频率最低的 k 个，一个常见技巧是存入(-freq, num)，利用取负把小顶堆变成大顶堆。347 题不需要这个技巧，但相邻题型 692（前 K 个高频单词）有类似逻辑，值得一并掌握。

还要注意heapq只保证堆顶是最小值，不保证整个列表有序。如果直接打印 heap，顺序会让人疑惑，这是正常现象。刷 LeetCode 不需要输出有序结果，所以没问题。

另一个坑：在堆元素不足时没检查堆长度，直接比较freq > heap[0][0]，会报IndexError。这是最简单也最容易犯的错误，每次写堆类题目我都要提醒自己先判断堆长度。

6.3 实际刷题中的测试用例参考

我调试这道题时固定用这几个用例，建议你也跑一遍：

这几个用例覆盖了最大频率、单元素、负数、k 等于全量等边界条件，跑通了基本不会有逻辑遗漏。

6.4 这个题目怎么横向扩展复习

347 题可以串起好几道经典题目：215 题“数组中的第K个最大元素”是纯快速选择/堆选择，421 题“数组中两个数的最大异或值”也用到前缀树+贪心思想，692 题“前K个高频单词”则在排序规则上加了字典序要求。我建议集中刷一遍，体会不同题目如何复用“统计频率 + 堆/分区”这个模板。

个人体会是：347 题最核心的价值不是那道题本身，而是让你把“求前K个”这类问题彻底吃透。面试中“求Top K”的变体非常多，底层思路通通指向堆或快速选择，把这两个工具的复杂度特征和代码模板练熟，远比记住单一题目的输出更重要。工具本身不会告诉你用哪个，真正决定方案的是数据规模和场景特点，这也是为什么我在这篇文章里反复强调复杂度分析的原因。