力扣第 347 题“前 K 个高频元素”是我刷题时印象特别深的一道题。它表面上只是“统计频率、取前 K 个”的简单逻辑但官方要求时间复杂度必须优于 O(n log n)一下子把最常见的排序思路给堵死了。很多人第一次做这道题都会愣一下不排序还能怎么做于是哈希表、堆、桶排序、快速选择这些内容全被串了进来难度不高信息量却不小面试出场率也一直很高。这篇内容就围绕这道题拆开讲适合准备算法面试、正在刷力扣热题或者工作中要处理 TopK 类问题的朋友。我会把三种主流解法的思路、代码、复杂度、边界坑一次说清楚顺便聊聊我自己踩过的几个坑。1. 题目到底在问什么别急着写代码1.1 两个关键词先看懂“前 K 个”和“高频”题目给一个非空整数数组要求返回出现频率前 k 高的元素。比如[1,1,1,2,2,3]这个数组1 出现 3 次2 出现 2 次3 出现 1 次如果 k 2答案就是[1,2]。这里有两个关键点容易忽略第一是“前 k 个元素”不是“频率恰好等于某个值的元素”所以 k 是一个数量限制第二题目并没有要求答案按频率降序排列只是让你把这 k 个元素找出来。这个“顺序无关”的设定很友好后续很多实现都可以省掉一次排序。还有一点要注意题目假设 k 总是合理的满足1 ≤ k ≤ 数组中不相同的元素的个数。也就是说 k 一定小于等于去重后的元素数量不会出现 k 大于不重复元素个数这种无解情况。很多人刷这道题时会忽略这个约束自己写测试用例时把 k 设得很大导致堆的返回结果不足 k 个然后开始怀疑算法写错了。其实这是审题问题不是代码问题。1.2 为什么“先排序”不是最优解绝大多数人拿到题的第一反应是用哈希表统计每个元素的出现次数然后按次数从高到低排序最后取前 k 个。这个思路完全正确逻辑上也通顺但有个硬伤时间复杂度是 O(n log n)而题目明确要求“你的算法的时间复杂度必须优于 O(n log n)”。很多人看到这里会有疑惑排序是 O(n log n)题目要求优于 O(n log n)这俩不是差不多吗严格说“优于”意味着严格小于排序的复杂度跟这个阈值一样不满足要求。面试时如果你一上来就写排序面试官大概率会追问一句“能不能别排序”目的就是考察你有没有掌握堆、桶排序或者快速选择这些更优的手段。所以这道题真正想练的不是统计频率而是如何在统计完频率后用低于排序的时间复杂度挑出 TopK。既然不能用全排序那有哪些思路我平时会分三种情况记如果 k 比较小用堆时间复杂度 O(n log k)如果数据规模特别大且频率分布均匀用桶排序时间复杂度 O(n)如果对平均复杂度有执念用快速选择平均 O(n)。下面一个一个说。2. 方法一哈希表 最小堆面试最稳解2.1 思路一句话先数次数再维护大小为 k 的小顶堆这个方法最符合直觉也是我面试时最常用的。分两步第一步用哈希表统计每个数字出现的次数第二步遍历哈希表用一个大小为 k 的最小堆维护“当前出现次数最多的 k 个元素”。堆的做法其实有点像班级里选成绩最好的前 K 名你手里只保留一个能坐 K 个人的名单新来一个同学如果成绩比名单里最差的那个好就把最差的踢出去让新人进来。具体到这道题堆里存的是(次数, 数字)这样的元组。为什么把次数放前面因为 Python 的heapq默认按元组第一个元素比较大小而我们要比较的核心是频率不是数字本身。如果写成(数字, 次数)堆顶会变成数字最小的元素整个逻辑就全乱了。这个细节我后面单独展开说。2.2 完整实现Counter heapq直接看代码from collections import Counter import heapq def topKFrequent_heap(nums, k): freq Counter(nums) heap [] for num, cnt in freq.items(): heapq.heappush(heap, (cnt, num)) if len(heap) k: heapq.heappop(heap) return [num for _, num in heap]这段代码很短但每一步都有讲究。Counter(nums)一次遍历就统计完所有元素的频率底层是哈希表。然后遍历freq.items()注意这里每个元素拿到的顺序是(数字, 次数)我们压入堆的时候要反转成(次数, 数字)。每次压入后检查堆大小超过 k 就弹出堆顶。因为是最小堆堆顶永远是当前堆里频率最小的那个也就是“最菜的”把它弹掉之后堆里剩下的就是目前最强的 k 个。最后用列表推导式把堆里的数字取出来返回顺序是任意的不需要再排序。如果题目要求按频率降序输出最后再加一步heap.sort(keylambda x: ...)或者直接取堆再排序都行但那属于额外需求原题不需要。2.3 为什么用最小堆而不是最大堆这是新手最容易卡住的问题。很多人直觉上会觉得既然要找高频元素那应该用最大堆把频率大的元素放在堆顶方便取出来。但如果用最大堆你必须把所有不重复元素全部压入堆复杂度变成 O(n log n)而且空间也是 O(n)。这样不仅没有发挥堆的优势反而又回到了不满足题意的复杂度。最小堆的思路是“维护一个冠军候选池”池子大小固定为 k堆顶是池子里最弱的那个。每来一个新元素只需要跟最弱的比如果比最弱的还弱说明它连前 k 都进不了直接忽略如果比最弱的强就淘汰最弱的把新人加进来。这样就保证池子里的 k 个元素始终是当前扫过的所有元素里最强的 k 个。整个过程每个元素最多进堆一次、出堆一次堆操作每次 O(log k)所以总复杂度是 O(n log k)。这里可以再补一个生活化的类比公司年会抽奖奖品只有 k 份主持人念一个名字你觉得这个人够不够资格进候选名单只需要跟当前名单里“最不像获奖者”的那个人比一下。名单永远只有 k 个人省时省力。2.4 复杂度分析与高频细节提醒时间复杂度遍历数组统计频率 O(n)遍历去重后的元素每个元素压堆、弹堆都是 O(log k)总共 O(n log k)。因为 k 通常远小于 n所以这个复杂度比全排序好不少。空间复杂度哈希表 O(n)堆 O(k)合起来 O(n)。有几个细节我必须专门提醒。第一Counter和普通字典的区别Counter在访问不存在的键时返回 0统计起来更顺手但它的items()顺序是插入顺序跟频率无关所以不能依赖遍历顺序。第二如果直接用freq {}统计时要用freq[num] freq.get(num, 0) 1效果一样。第三堆里存元组虽然简单但遇到两个元素频率相同的情况heapq会比较第二个元素也就是数字本身这就可能导致堆顶不是你预期的那一个。不过这里没关系因为我们只关心频率大小频率相同谁进谁出不影响最终集合的正确性。还有一个工程上的小优化如果 k 已经等于去重后的元素个数那其实直接返回所有键就行不需要走堆的逻辑。虽然堆也能处理但会白白浪费 O(n log k) 的时间。我在力扣提交时会加一行判断if k len(freq): return list(freq.keys())能省一点是一点尤其在数据量很大的测试用例上这个判断能明显缩短运行时间。3. 方法二桶排序把 log 因子直接去掉3.1 思路用“频率”本身做桶下标堆的解法已经能通过力扣了但如果你追求理论上的最优复杂度可以试试桶排序。为什么能到 O(n)因为数组长度为 n所以每个元素的出现次数必然在 0 到 n 之间。我们可以把“频率”当作桶的下标把出现次数相同的元素扔进同一个桶里最后从高频率的桶往低频率的桶遍历收集元素直到拿满 k 个为止。这个思路的理解门槛稍微高一点但代码其实特别短。核心是不需要排序也不需要比较频率即索引。就好比考试成绩出来之后老师不想逐个排名而是按分数把试卷分到几个筐里100 分的放一筐99 分的放一筐最后从高分筐往下拿试卷拿够 k 张就行。3.2 完整实现用 defaultdict 建桶先上最直接的版本from collections import Counter, defaultdict def topKFrequent_bucket(nums, k): freq Counter(nums) bucket defaultdict(list) for num, cnt in freq.items(): bucket[cnt].append(num) res [] for cnt in range(len(nums), 0, -1): if cnt in bucket: res.extend(bucket[cnt]) if len(res) k: return res[:k] return res[:k]这里bucket是一个字典键是频率值是该频率对应的所有数字列表。统计完频率后从len(nums)开始往下遍历到 1一旦发现某个频率有元素就把它整批加入结果。为什么从len(nums)开始因为最极端的情况下所有数字都相同某个元素的频率正好等于 n所以桶下标最大就是 n。倒序遍历保证我们优先取高频元素。defaultdict(list)的使用比普通dict安全很多访问不存在的键时自动创建一个空列表不需要手动setdefault。如果你不用defaultdict也可以写成bucket.setdefault(cnt, []).append(num)效果一样。3.3 为什么桶排序能碾压堆边界怎么处理在数据量特别大的场景下桶排序的优势非常明显因为它的时间复杂度是严格的 O(n)连 log k 的因子都去掉了。比如 n 一千万k 100堆的做法是一千万 * log 100次比较桶排序大概就是一千万次哈希操作加一千万次遍历性能差距是实打实的。但桶排序也不是没有代价它的空间占用可能比堆更大。最坏情况下如果每个元素频率都不相同bucket里会有 n 个键每个键对应一个只有一个元素的列表这样空间上其实还是 O(n)跟哈希表差不多。而堆的空间是 O(k)在 k 很小的时候堆的内存表现更好。实际写的时候桶排序还有一个常见问题很多人习惯用定长列表来当桶比如bucket [[] for _ in range(len(nums) 1)]这样做没问题但即使很多桶空着也会一次性占满内存。如果数组长度很大而不同频率很少用defaultdict(list)会更省。我用过的一个百万级测试用例定长列表的初始化时间和内存都会多出不少改成defaultdict之后明显更轻。边界方面需要注意 k 等于不同元素个数时的情况。比如[1,2,3]k 3每个元素频率都是 1此时倒序遍历只会走到cnt 1的桶把三个元素全部放进去返回res[:3]刚好满三个逻辑是对的。而如果 k 比实际不重复元素个数还大题目说了不会出现这种情况所以不用考虑。3.4 面试里怎么讲桶排序才加分桶排序的代码很简单但面试官更想听到的是“为什么能用桶”。我会在解释时说清楚一个前提频率的取值范围是有限的正好是 0 到 n所以能建立“频率 → 元素列表”的映射。这种利用数据范围把排序退化成计数的思路其实就是计数排序的变种。面试官追问“还有更快的吗”时你抛出桶排序他会觉得你是真的理解了复杂度而不是背题。但也要注意桶排序依赖元素的频率都是正整数且范围有限。这道题里元素可以是任意整数但我们统计的是次数次数天然落在 0 到 n所以桶排序完全适用。如果换成浮点数、字符串桶排序就不是首选了因为没法直接用次数做下标。这一点讲清楚了面试官会对你更有信心。4. 方法三快速选择平均 O(n) 的分治思路4.1 从快排 partition 说起只需要一半的信息如果不想用堆也不想开一堆桶还有一条更“硬核”的路快速选择。很多人对快速排序很熟知道它每次 partition 能把一个元素放到最终位置。快速选择的思路是既然我们只关心前 k 个那不需要整个数组有序只需要找到“第 k 大”的位置并且保证它左边的元素都大于等于它就行。这样每次 partition 之后只需要递归或循环处理包含 target 的那一侧另一侧直接丢掉。我举个生活化的例子你要在一堆试卷里找出分数最高的前 10 张不用把所有试卷按分数排好序只需要随便抽一张试卷把比它分数高的放左边、比它低的放右边。如果左边正好 9 张那这张试卷加上左边 9 张就是前 10。如果左边有 20 张那目标缩到左边继续找如果左边只有 3 张那这 3 张已经确定入选再在右边找剩下 7 张就行。快速选择每次都能扔掉一半数据平均效率很高。4.2 完整实现按频率做随机 partition这道题里我们要排序的不是元素本身而是元素的频率。所以先把所有不重复元素和对应频率取出来然后对频率数组做快速选择同时保持频率和元素的对应关系。from collections import Counter import random def topKFrequent_quickselect(nums, k): freq Counter(nums) unique list(freq.keys()) counts [freq[num] for num in unique] def partition(l, r): pivot_idx random.randint(l, r) pivot counts[pivot_idx] counts[pivot_idx], counts[r] counts[r], counts[pivot_idx] unique[pivot_idx], unique[r] unique[r], unique[pivot_idx] store l for i in range(l, r): if counts[i] pivot: counts[store], counts[i] counts[i], counts[store] unique[store], unique[i] unique[i], unique[store] store 1 counts[store], counts[r] counts[r], counts[store] unique[store], unique[r] unique[r], unique[store] return store l, r 0, len(unique) - 1 target k - 1 while True: pos partition(l, r) if pos target: return unique[:pos 1] elif pos target: l pos 1 else: r pos - 1这段代码比前面两个长但逻辑并不复杂。partition做的事和快速排序一模一样随机选一个 pivot把频率大于 pivot 的元素放到左边小于等于 pivot 的放到右边最后返回 pivot 在最终排序数组中的位置。因为我们要找的是前 k 高所以 target 就是k - 1代表第 k 高频率元素应该在的下标。每次 partition 后如果 pivot 位置正好等于 target那 pivot 左边所有元素加上 pivot 自己就是前 k 个。随机化的作用非常重要。如果不随机选 pivot每次固定选第一个当数据恰好是逆序时partition 的切分极不均匀复杂度会退化到 O(n²)。随机化之后虽然理论上仍然存在最坏情况但概率低到可以忽略期望复杂度是 O(n)。4.3 为什么平均是 O(n)最坏却是 O(n²)快速选择的复杂度分析是面试高频考点。假设每次 partition 都能把区间分成大致相等的两半那么第一轮处理 n 个元素第二轮处理 n/2 个第三轮 n/4 个总工作量是 n n/2 n/4 ... 2n所以期望复杂度是 O(n)。这比堆的 O(n log k) 更优因为去掉了 log 因子。最坏情况发生在极端不平衡的切分比如每次 pivot 都是当前区间的最小值那每次只排除一个元素总工作量变成 n (n-1) (n-2) ... O(n²)。虽然随机化可以让这种情况概率非常低但从算法理论角度看最坏复杂度仍然是 O(n²)。面试时如果你主动说出这一点并且补充“所以工程上经常用随机化或者中位数策略来规避退化”会显得思考更全面。4.4 快速选择最容易翻车的三个细节第一个细节数组对应关系。unique和counts必须同步交换只换counts不换unique最后返回的数字就会张冠李戴。我在第一次实现时就漏了这一步结果频率排序正确但返回的元素全错排查半天才发现问题。第二个细节partition 的比较符号。如果我们希望最后返回的是“频率降序”下的前 k 个那么 partition 时要把大于 pivot 的放左边小于等于 pivot 的放右边。注意这里用的是不是这样能避免大量相等元素在分区时过度集中也能减少一些无意义的交换。当然用也不会出错只是可能多花费一点时间。第三个细节while 循环退出条件。如果pos target说明前 k 个元素的第 target 个还在右边需要把左边界移到pos 1如果pos target说明我们已经把多余的更高频元素放到了左边需要把右边界移到pos - 1。千万别把l和r的更新方向写反否则会死循环或者返回错误结果。5. 常见坑与排查我把能踩的坑都踩了一遍5.1 堆里存元组的顺序问题这个方法我单独拿出来说因为它真的坑过很多人。Python 的heapq对元组比较时先比较第一个元素如果相等再比较第二个元素。所以如果你写成(num, cnt)堆的比较基准就变成了数字大小而不是频率。比如(1, 5)和(2, 3)heapq会认为(1, 5)更小因为 1 小于 2然而 5 的频率明明更高。这样整个堆的维护就完全失去了意义。正确写法是(cnt, num)。如果你确实想让代码更可读也可以用自定义类class FreqNode: def __init__(self, num, cnt): self.num num self.cnt cnt def __lt__(self, other): return self.cnt other.cnt然后往堆里放FreqNode(num, cnt)。但这个写法在力扣上会有一些额外的性能开销而且代码更长。日常刷题直接用元组就够了但要在脑子里明确知道比较顺序。5.2 k 与不同元素个数的边界问题边界测试非常考验代码严谨性。Counter统计后不同元素个数是len(freq)如果 k 等于这个值堆解法里堆永远不会满到超过 k所以最后返回堆里所有元素逻辑正确桶排序里需要倒序遍历到频率 1 的桶把全部元素收集返回也正确。但如果你在堆解法中加了“堆大小超过 k 就弹出”的逻辑而 k 正好等于不重复元素数那整个过程中堆都不会触发弹出最后堆里的元素就是全部元素。比如nums [1,2,3]freq {1:1, 2:1, 3:1}k3最后返回的堆里是(1,1),(1,2),(1,3)三个元组数字部分正好是[1,2,3]。这种情况不会报错但新手往往会怀疑“堆没有弹出是不是有问题”。其实没问题正是因为堆始终没超容量。5.3 负数和 0 会让桶排序出问题吗不会。因为桶排序的下标是“频率”不是“元素值”。比如nums [-1, -1, 0, 2, -1]Counter统计结果可能是{-1: 3, 0: 1, 2: 1}频率分别是 3 和 1桶下标只可能是 0、1、2、3、4、5 这些非负整数。所以负数元素并不会干扰桶的索引。真正需要注意的反而是那些没出现过的频率对应的空桶遍历时要跳过。快速选择同样不用担心负数因为它操作的是counts数组元素值只存在于unique数组里partition 比较的是频率而不是数字。唯一要注意的是unique和counts的下标对应关系前面已经强调过。5.4 输出顺序到底要不要管原题允许“任意顺序返回答案”所以三种方法直接返回都可以。但我也遇到过一些面试官在追问时改成“请返回降序排列的结果”这时候就有区别了堆方法可以在返回前对堆里的元素按频率从大到小排个序桶排序反正已经按频率从高到低取桶了结果天然有序快速选择返回的前 k 个并没有保证全局降序还需要对这 k 个元素再排一次。这里有一个很常见的误解快速选择返回的unique[:pos 1]其实只是“前 k 个高频率的集合”并不是严格降序排列的列表。因为 partition 只保证 pos 左边都大于 pivot但左边内部是无序的。所以如果面试题要求降序快速选择做完后还得对这 k 个元素按频率快排或堆排。我在力扣题目中不需要处理这一步但如果你用自己的测试脚本对比结果时发现输出顺序不同不用慌那不代表算法实现错。5.5 性能实测不同数据下怎么选我习惯在刷完题之后用大测试用例实测一把看看三种方法的真实表现。有一组数据我记得很清楚一个长度为 100 万的数组里面 80% 是重复数字k10。堆解法用时大约 0.4 秒桶排序大约 0.25 秒快速选择大约 0.2 秒。但当 k 增大到 50 万时堆解法因为log k变大明显变慢快速选择依然很快桶排序则要看内存分配情况。还有一个反直觉的现象如果 k 接近len(freq)堆解法反而比桶排序更快因为堆几乎不用弹出操作而桶排序仍然要遍历所有可能的频率桶。所以我总结了一个选型心法刷题求稳选堆因为代码简单、不依赖随机数、不会被极端用例卡到 O(n²)追求极致性能选快速选择或桶排序但快速选择要考虑随机化桶排序要考虑内存。实际工程中如果数据量特别大比如日志分析里统计 TopK 关键词我更倾向于用堆因为内存可控而且流式数据天然适合堆。6. 延伸思考这道题和真实世界的 TopK 问题刷题从来不只是为了过提交。力扣 347 的解法放到真实业务里就是经典的 TopK 问题。我做过后端日志分析要统计一天内访问量最高的 100 个接口做过推荐系统的标签统计要从海量行为日志里找出出现频率最高的标签还做过舆情监控要快速找出高频敏感词。这些场景的数据量可能比力扣测试用例大得多但解法思路完全一致先哈希统计再堆/桶/快选挑 TopK。差别在哪真实系统里的数据往往不是一次性给完的而是持续流入的。比如日志一条一条来你可能没法先全部加载到内存再统计。这时候哈希表加堆的方案也就是方法一天然适合流式处理每来一条数据更新哈希表如果这个元素的频率变化导致它应该进入堆就更新堆如果不在堆里但比堆顶大就替换。整个过程只需要维护哈希表和一个大小为 k 的堆内存占用可控很适合在线场景。桶排序和快速选择则更适合离线批处理。桶排序的优势是频率范围已知且有限但内存消耗大数据量超过内存上限时会很尴尬。快速选择适合一次性从内存中取数的场景但不能流式处理因为每来一个新数据整个频率排序可能都被打乱。理解了这些延伸你再看这道题就不会觉得它只是“一道力扣题”而是很多真实 TopK 问题的抽象原型。我自己刷完这道题后的一个习惯是把三种解法都封装成函数然后用随机数组互相验证结果是否一致。这样既能验证算法的正确性又能对比性能。你如果刚开始刷题我建议也这么试一次比单纯背代码有用得多。最后再分享一个小技巧遇到 TopK 相关题目时先问问自己 k 是大还是小、数据是静态还是流式、是否允许额外空间这三个问题答案基本能帮你锁定解法不用硬背模板。
