企业官网建设流程全解析

刷LeetCode Hot 100的人，十有八九会在第347题《前K个高频元素》这卡一下。不是因为它难，而是因为它的解法多到你不知道该背哪个：堆、快速选择、桶排序，每种解法都能写，但面试时到底该讲哪一种？我用这道题反复练了很多遍，今天把完整的拆解思路和实战踩坑记录整理出来，希望能帮你一次吃透它。

1. 题目拆解与从暴力到有序的思考路径

347题本身描述很简单：给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。示例输入[1,1,1,2,2,3], k=2，输出是[1,2]。

但这道题真正的考点不在统计，而在"排序"那一步。统计是O(n)跑不掉的，但怎么从统计结果里挑出前K个，才是拉开差距的地方。

我刷题有个习惯：拿到题先不看题解，自己把能想到的解法全写一遍。这样做有个好处，就是你对"为什么需要更优解"有真实的感知，而不是背下来的复杂度结论。

1.1 题目到底在问什么：先看清楚问题的边界

这道题有几个边界条件值得先想清楚：

• k的范围：题目确保k合法，且1 <= k <= 数组中不同元素的个数，这让代码少了很多防御性判断。
• 返回值顺序：题目只要求返回元素，不要求按频率排序，这给了快速选择类算法空间。如果你用排序，那就是杀鸡用牛刀。
• 原始顺序：输入数组的元素顺序对结果没有影响，关键是频次，和题目背景里的"热搜词hot100题"这类场景类似，热搜榜单看的也是热度而非时间顺序。
• 元素范围：nums中元素值可能为负数，不能直接用值做数组下标做桶，必须先做哈希映射。

我把这几点列出来是因为它们直接决定了主解法的选择。比如"不要求有序输出"意味着你可以用快速选择到O(n)平均复杂度；如果要求有序输出，那你后面还得补一次排序，复杂度就重新变成O(nlogn)了。

1.2 暴力解法：哈希统计加全量排序为什么慢

最直觉的做法是两步走：先遍历数组，用哈希表把每个元素出现的次数记下来；再对哈希表的所有键值对按value做降序排序，取前k个。

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

这段代码能过题，但它的时间复杂度是O(n + mlogm)，其中m是不同元素的个数。当m接近n时，整体就是O(nlogn)。

问题是：我们只需要前k个，却把所有元素都排了序。前面那些低频元素明明不关心，对不对？这就像公司要评出业绩前3名，你不会把全公司几千人做一次完整排名，而是一轮轮淘汰，最后只保留前几个候选人。暴力解法的冗余就在这。

换个角度想，Top K问题的核心矛盾是：k通常远小于n，可排序却让复杂度被n而不是k主导。优化方向就明确了——能不能把复杂度压到O(n logk)甚至O(n)？下面三种主流解法，分别是在"堆""快速选择""桶"这三个思路上优化。

2. 堆解法：为什么K大小的小顶堆是默认答案

如果你去查这道题的题解，十个有九个会给你堆的写法。原因很简单：它思路直观、代码短、复杂度稳定，而且在Java、C++的面试里，手写堆不会出幺蛾子（Python直接用heapq，C++用priority_queue）。

但我第一次看堆解法时有一个困惑：为什么是"小顶堆"而不是"大顶堆"？直觉不是反了么，要前K高频，不该用大顶堆每次都弹出最大的吗？

这个困惑恰恰是堆解法的精髓。

2.1 堆筛选的核心思路与代码实现

如果你用大顶堆，思路是这样的：把哈希表里所有键值对丢进一个大顶堆，然后连续弹出k次，每次堆顶都是当前最大。但这样做的堆大小为m（不同元素个数），建堆O(m)，每次弹出O(logm)，整体复杂度是O(n + m + klogm)。在m = n时，退化成了O(nlogn)，和暴力排序没有本质区别。

小顶堆的思路反过来了。我只维护一个大小为k的堆，每个元素进来都和堆顶比：如果比堆顶（当前堆里的最小频率）大，就把堆顶替换掉。

这样做的好处是堆里永远只有k个元素，所有操作都是O(logk)，总时间复杂度是O(n logk)。当k远小于n时，这就是数量级的差距。

import heapq def topKFrequent(nums, k): freq = {} for num in nums: freq[num] = freq.get(num, 0) + 1 heap = [] for num, count in freq.items(): if len(heap) < k: heapq.heappush(heap, (count, num)) elif count > heap[0][0]: heapq.heapreplace(heap, (count, num)) return [item[1] for item in heap]

注意细节：堆里的元素是(count, num)元组，heapq默认按元组第一个元素排序，所以堆顶就是当前k个候选里频率最小的那个。只要来一个频率更大的，就把它替换出去。一轮循环下来，堆里留下的自然是全局前k高频。

2.2 复杂度、稳定性与面试追问

堆解法的时间复杂度是O(n logk)，空间复杂度是O(n + k)（哈希表占用O(n)，堆占用O(k)）。

面试官如果在堆解法上追问，通常有三个方向：

1. 为什么用heapreplace而非heappush加heappop两步？因为heapreplace在堆不为空时相当于先pop再push，但只有一个操作，常数更小，且更语义化地表达了"替换"的意图。
2. 如果k接近n怎么办？这时O(n logk)趋近O(nlogn)，堆解法优势消失，应该反过来想，维护一个大小为n-k的堆找出"低频"的，再取剩余部分。当然实战里面这个边界很少见。
3. 堆元素再多一个维度怎么处理？如果频率相同按值大小排序，只需要把元组换成(count, -num)或自定义比较器。Python的heapq不支持自定义比较器，简单的技巧是存(-count, -num)或(count, num)调整顺序。

我在面试中被问过更细的问题：如果数据是流式的，源源不断进来，堆解法还能用吗？答案是可以的，因为堆天然支持动态add和pop，每次进来一个新元素，更新计数，再维护堆的size不超过k，整个过程是O(logk)。这种场景叫"数据流TopK"，后面第五节我会展开讲。

3. 快速选择：从无序到O(n)平均复杂度的进阶解法

如果你觉得堆解法已经够了，那这道题剩下的一半价值就被你漏掉了。347题还有一个隐藏得很深的考点：它本质上是一个"按频率找第k大"的问题，而这个"找第k大"恰恰是快速选择（QuickSelect）的用武之地。

3.1 快排思想如何改造成TopK筛选

大多数人对快排的记忆停留在"分治排序"，但它其实还有一个更厉害的应用：每次partition后，基准元素（pivot）已经落到了最终位置。如果pivot的下标正好是len(freq) - k，那pivot右侧（含pivot）的所有元素就是前k个最大的。

这就把问题从"排序所有元素"变成了"只关心基准位置"。每一轮partition都砍掉一半不需要处理的数据，平均情况下只需要O(n)次比较。

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

这里的target = n - k是第k大元素在升序数组中的正确下标，我一开始就直接做第n-k小的快速选择，比"先找最大再删掉"的写法干净得多。partition完成后，items[target:]就是频率最高的k个元素。

3.2 partition细节、基准选择与退化问题

这段代码在面试里容易翻车的点有三个：

• 基准选择：经典实现普遍选最后一个元素做pivot，如果数据碰巧有序，每轮partition都只消掉一个元素，退化到O(n²)。要规避的话，可以在left和right之间随机选一个下标，和items[right]交换后再partition。我实测过，同样是顺序数组，固定pivot会超时，随机pivot稳定通过。

• partition的等号处理：这段代码里，items[j][1] < pivot的元素被换到左边，等于pivot的元素不动。如果数据里有很多相同频次，最终pivot的落点可能出现在target附近，但循环判断是idx == target才停，没问题的。但如果你的实现里用了<=，那partition后左右两侧元素的分布会变化，target的含义也要跟着调，很容易写出bug。

• 返回值是否有序：快速选择返回的前k个元素，内部是无序的。这点和题目要求一致，但如果你在工程里需要有序输出，需要在返回前对结果排序，那总复杂度就变成了O(n + klogk)。有人会因此否定快速选择的优势，这属于混淆了需求。题目没要求有序，你为了有序输出额外排序，是把需求变了。

3.3 完整代码与对比分析

为了让你更直观地选择，我整理了一份两种解法的对比：

快速选择的最坏情况是个隐患。面试时我通常这样圆场：用随机化基准可以把最坏情况出现概率降到极低；如果面试官非要确定性O(n)，那就得讲BFPRT算法了，这个可以作为加分项提一嘴，但不建议真的在面试里写完整实现，篇幅和容错率都不划算。

4. 桶排序：频次映射带来的另类最优解

堆和快速选择是这道题的"标准答案"，但如果你只知道这两条路，那遇到数据范围特殊的变种题，你可能就会绕远路。347题还有一个很巧的桶排序思路，它的适用条件是"频次范围有限"，这在很多真实场景里恰恰成立。

4.1 桶排序的适用边界

桶排序的核心观察是：一个元素在数组里最多出现n次，最少出现1次。那我可以建一个长度为n+1的桶数组，下标代表频次，桶里装的是所有出现该频次的元素。

然后从桶数组末尾（频次最高的桶）往前遍历，取非空桶里的元素，直到拿够k个。

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

这个解法的时间复杂度是O(n)，空间复杂度是O(n)。它和前两种思路的差别在于：桶排序不做任何比较，用下标直接定位频次，所以能突破比较排序的下界。虽然题目给的数据范围用不上这个优势，但在"频次有界"的场景里，它就是理论最优。

4.2 代码实现与内存开销

桶排序的实现简单到几乎不可能写错，但有两个细节值得注意：

• 桶数组的长度是len(nums) + 1，不是max(freq)，因为极端情况下某个元素可能出现n次，下标要够用。
• 从频次最高的桶开始遍历时，桶内部的元素顺序无所谓，因为题目不要求有序输出。如果要求有序，桶内排序会给已经O(n)的算法增加额外开销，不过那就是改需求了。

我还遇到过一个变种题：nums里元素值是0 <= nums[i] <= 100，这时可以直接用值做下标，统计频率后按"值从小到大"输出前k个高频。这本质上还是桶，但桶变成了固定大小，比通用写法更省空间。这种变种题网上流传很多，思路都是一样的。

讲句实话，桶排序在347题里算是"炫技"解法，面试官预期通常就是堆或快速选择。但如果你能在讲完堆之后补一句"如果频次范围有限，可以用桶排序把复杂度降到稳定O(n)"，会显得你脑子里有一张完整的算法谱系，而不是只背了一道题。

5. 实战中如何选型与TopK问题的扩展谱系

刷透了347题，真正的收获不是会做这一道题，而是建立起一个Top K问题的决策框架。以后凡是看到"前k个最大/最小/最频繁"，你脑子里应该自动弹出下面这张表。

5.1 不同场景下的解法选择

最后一行值得展开说。真实的大数据场景里，数据不可能全在一台机器上。通常的做法是每一台机器各自统计词频，然后各机器维护一个大小为k的堆，最后把所有机器的堆结果汇总再做一次堆合并。这其实就是堆解法在分布式环境下的自然延伸，347题的表现形式直接套用就能理解这个系统设计。

我实习时做过一个日志分析的需求，要实时统计过去一小时访问量最高的10个接口。当时我用的方案就是每台机器维持一个小顶堆，定期把堆上报到聚合层，聚合层再合并出全局Top10。你说这和347题有什么关系？关系大了，除了数据是流式的、需要滑动窗口之外，筛选逻辑完全一致。

5.2 数据流、分组TopK等扩展

顺着数据流这个方向，347题的扩展题五花八门，我整理几个典型的：

1. 数据流TopK：数字不断进来，随时查询当前出现频率最高的k个数。解法是哈希表计数+小顶堆，新增元素时更新计数，如果它在堆里，要同步调整堆；如果不在堆里且堆没满，直接入堆；堆满了且新频次比堆顶大，替换堆顶。这里有个坑：元素已经在堆里时，heapq不能直接更新它的计数值，需要先标记再重新push，或者干脆惰性删除。惰性删除就是在堆里存(count, num, version)，每次更新时version加1，堆顶如果version过期就直接pop。这个技巧我在工程里用过很多次，比"支持更新的索引堆"好写得多。

2. 分组TopK：比如按用户分组，每个组内取消费金额最高的前3笔订单。实现上可以先按组哈希，组内用小顶堆，逐组处理。这在SQL里就是ROW_NUMBER() OVER(PARTITION BY user_id ORDER BY amount DESC)，但如果在内存计算引擎里手写，堆还是主武器。

3. 第K个最大元素的变体：LeetCode 215就是纯纯的"数组中的第K个最大元素"，和347的区别只是少了一层哈希统计。刷347之前先做215会顺很多，因为partition的代码完全一样。

4. 出现频率超过n/k次的所有元素：这个问题叫"多数元素"（LeetCode 169是n/2版本，229是n/3版本）。官方最优解是摩尔投票，不用哈希不用堆，O(1)空间。但它其实也是"频率TopK"的一个特例，只不过k= n/k让人困惑，这里k不是候选数量，而是频率阈值。

把这些串起来看，347题就像是TopK家族的一个枢纽节点——往左边延伸是"第K大"的快速选择，往右边延伸是"数据流TopK"的堆维护，往下延伸是"有限频次"的桶归类。所以很多人说Hot 100刷到70以后会出现"做一题顶三题"的感觉，347就是典型的刷题枢纽。

5.3 我的刷题与面试经验

最后分享几点个人的刷法。我第一次做347时，直接看了堆解法就背了下来，当时觉得自己会了。结果过了两周在面试里碰到类似题，让我讲"为什么不是大顶堆"，我愣了三秒没接上话。从那以后我给自己定了个规矩：每道题不仅要写出来，还要能回答"为什么是这个数据结构""为什么是这个方向""复杂度差在哪里"这三个问题。

347这道题我推荐至少刷三遍：

• 第一遍：只看题目，20分钟内用堆解法AC。
• 第二遍：隔三天再做，要求自己想出快速选择的写法，并分析最坏情况。
• 第三遍：隔一周再做，要求自己从"TopK问题家族"的角度，一口气说出堆、快速选择、桶排序的适用边界，以及数据流场景的改造方案。

三遍过后，这道题才真正属于你。别嫌重复，Hot 100的价值恰恰在于这些题目互相之间有一张知识网络，347是网络里的一个关键节点，把它的周边全部点亮，你在刷215、295、373等一票兄弟题时都会轻松一大截。