前 K 个高频元素六个字一个在面试中被反复拎出来考的经典问题。任何认真刷过一阵子题的人早晚都会撞上它。我之前带一个刚转行的朋友刷题打到这道题时他卡了很久因为他发现网上的题解一会儿用堆、一会儿用快选、一会儿用桶看起来思路五花八门看完反而更懵了。其实这道题并没有那么玄乎它的难点不在算法本身而在于你到底有没有理解“Top K”这类问题背后那套统一的筛选逻辑。今天这篇就把这道题彻底拆开讲从审题到三种主流解法再到真实业务里的变形争取让你看完之后不光会写这一道题还能顺手把一整类题都吃透。这道题适合谁看准备面试的求职者、正在刷题找手感的开发者、以及工作中要处理“排行榜”“热点统计”这类需求的工程师。我会先把题目的关键约束讲清楚然后按“从稳妥到风骚”的顺序给出三种解法最后聊聊代码之外的坑和真实场景落地时要注意的事情。1. 先读懂题前K个高频元素的三个关键点1.1 题干示例与隐藏假设题目本身的描述非常短给你一个整数数组和一个整数 K要求返回数组中出现频率最高的前 K 个元素。经典示例是nums [1,1,1,2,2,3]k 2输出[1,2]。就这对题干就这么简明。但越是简短的题越容易忽略隐藏条件。你需要确认三件事第一K 一定是合法范围内的正整数吗大多数版本里 K 是有效的但真实面试中建议先问一句“K 大于数组长度怎么办”或者“K 等于0怎么办”。这两个问题能体现你的边界意识至少能加一点印象分。第二返回顺序有要求吗原题说“可以按任意顺序返回答案”也就是说[1,2]和[2,1]都能过。但很多公司面试时会在白板上追问一句“如果频率相同的元素也要按某种顺序返回呢”这时候你的实现就要考虑比较器写法了。第三数组中元素的取值范围和数量级。如果值域非常有限桶排序的思路会更好写如果数组特别大内存受限那堆方案会更适合流式处理。这些都是在动手之前要在心里过一遍的东西。1.2 这题为什么是面试常客这道题在题库里的编号是 347属于那种“一眼能读懂、上手有难度、深挖有空间”的经典题。面试官喜欢它的原因很简单它考的不是某一个孤立算法而是“哈希表 堆”的组合应用同时又能延伸出快速选择、桶排序等一系列变体。你可以在三分钟内写一个暴力解也能用一个精妙的小根堆把空间压得很漂亮还能在追问环节聊到海量数据下的近似方案。一道题就能探出你数据结构和算法设计的基本功性价比极高。另外这道题背后对应着一大类真实业务需求热搜词统计、Top N 榜单、访问量排名、异常检测里的高频 IP。所以面试官从来不认为它只是一个考试题它更像一个很多系统都会用到的通用算法组件。理解这一层你写代码时的感觉会不一样。1.3 动手前的三分钟审题清单我每次做这道题之前都会在草稿纸上快速过一遍这个清单计算每个元素出现频率用哈希表做映射。明确“前 K 个高频元素”等价于“频率最大的 K 个”。确认 K 与不重复元素数量的关系K 最多等于不重复元素的个数。思考内存限制能不能一次性把哈希表放内存思考数据特性如果元素值域小选桶序更快如果数据是无限流直接选堆。这些看起来是细枝末节但恰好就是决定你在面试现场选哪种解法的关键。2. 解法一哈希计数加最小堆稳妥拿捏TopK2.1 整体思路先统计频率再维护一个大小为K的堆解法一的思路是最直觉的分两步走。第一步遍历一遍数组用哈希表统计每个数字出现的次数。这一步的时间复杂度是 O(N)空间复杂度是 O(M)M 是不重复元素的个数。第二步想办法从这 M 个“数字-频率”对里挑出频率最大的 K 个。如果直接对所有元素按频率排序时间要 O(M log M)。但题目只要前 K 个排序显然浪费了。这时候用堆就非常合适维护一个大小限制在 K 的堆遍历所有键值对堆里始终保留目前见过的频率最大的 K 个。为什么用堆而不是排序因为堆的插入和删除都是 O(log K)整体复杂度 O(M log K)。当 M 很大而 K 相对较小的时候这个方案比全量排序省得多。2.2 为什么是“最小堆”而不是“最大堆”这是很多人写第一版代码时最困惑的地方。直觉上我们要求“最大频率”那是不是该用最大堆错了这里恰恰要用最小堆。你设身处地想一下一个大小为 K 的堆容量有限。我们要让堆里留下来的都是“赢家”。如果这个堆是最大堆堆顶是当前最大的元素那新元素来的时候怎么判断它该不该进堆你得跟堆顶比而堆顶是最大的比它小的新元素进不去比它大的新元素又把堆顶顶掉——但顶掉的又是最大的逻辑就绕乱了。如果换成最小堆堆顶是堆里最小的那个也就是“当前所有候选者里最弱的一个”。新元素进来如果比这个最弱者还小那它肯定没资格占用一个名额如果比最弱者大那就把最弱者干掉自己上位。每一次操作都淘汰掉当前“最差”的候选者K 个名额里永远留着最强的 K 个。这样思路就顺了。用一句通俗的话总结你要选最优秀的 K 个人进一个只能容纳 K 人的微信群群里最差的那个人说了算新来的人只有比“群内最差”强才能踢掉他进来。2.3 Python代码实现与关键注释import heapq from collections import Counter def top_k_frequent(nums, k): # 第一步统计频率 counter Counter(nums) # 第二步维护一个大小为 k 的最小堆 heap [] for num, freq in counter.items(): heapq.heappush(heap, (freq, num)) if len(heap) k: heapq.heappop(heap) # 堆中剩下的就是频率最高的 k 个元素 return [num for _, num in heap]这段代码有几个细节值得注意。第一堆里存的是元组(freq, num)不是单独存频率。这样做的好处是堆比较时会先比较 freq如果频率相同再比较 num可以避免元素之间比较时报错。更关键的是我们需要 num 作为最后的输出结果把 num 一起放进元组弹出堆顶时才知道该踢掉的是哪个数字。第二先 push 再判断大小也就是“先无脑入堆超了就弹”。这也是一种实现方式。它的好处是代码更紧凑即使 K 等于 0也能通过先 push 再 pop 维持正确性。前提是 K 大于 0因为 K 为 0 时heapq.heappop(heap)会直接抛异常。不过题目通常会保证 K 合法。第三用 Python 内置的 Counter 不是为了偷懒而是因为它在底层用 C 实现统计频率那一段比手写 for 循环快不少。面试时你完全可以手写一遍逻辑但用 Counter 更贴近真实项目的写法。2.4 复杂度分析与典型边界哈希计数部分是 O(N)堆操作部分每个键值对做一次 push 和 poppush 是 O(log K)pop 也是 O(log K)最坏是 O(N log K)。空间复杂度主要来自哈希表 O(M) 和堆 O(K)通常记作 O(N)。这个方案最稳的地方在于不管数据是有序、无序、还是全部相同它的最坏复杂度都是可靠的不存在退化的情况。对于一场技术面试来说如果你不想冒险这个解法就是最安全的第一选择。但是在实际运行中我有一个经验K 非常小的时候比如 K 1动态 push/pop 其实比“全量排序后取第一个”还要慢一点点因为 Python 的排序是 C 层的高度优化实现。不过这只在极端小 K 的情况下有差别面试时别因为这个去跟面试官抬杠正常用堆就对了。3. 解法二快速选择把答案一步选出来3.1 换个角度频率数组的第K大堆解法已经足够好但它毕竟带了 K 的对数因子。如果面试官问“能不能再快一点”这时候就该快速选择登场了。快速选择的核心思想源自快速排序。快排每次选择一个基准值把数组分成小于基准和大于基准两部分然后递归处理两边。而快速选择只要一个分区的结果分完之后如果基准正好落在目标位置那么目标位置的左边都比它小、右边都比它大问题就解决了不需要像快排那样两边都递归。放到这道题里我们把哈希表统计结果转换成“频率数组”比如[3, 2, 1]分别对应示例中 1、2、3 的频率。要找前 K 个高频等价于找频率数组中第 M-K 小从 0 开始计数的元素位置。因为频率数组长度是 M第 M-K 小的位置之后就是最大的 K 个。3.2 分区函数怎么写才不会被退化成O(N²)快速选择最大的坑是退化。如果每次选的基准恰好是最小值分区后左边为空、右边几乎全保留那么它就会退化成 O(N²)。解决办法非常简单随机找一个元素当基准。随机化之后最坏情况仍然存在但实际出现概率极低平均复杂度能稳定在 O(N)。分区函数具体这样写def partition(arr, left, right): # 随机选基准避免最坏情况 import random idx random.randint(left, right) arr[idx], arr[right] arr[right], arr[idx] pivot arr[right][1] # 我们用第二项频率作为基准值 i left for j in range(left, right): if arr[j][1] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[right] arr[right], arr[i] return i这里的技巧是先把基准换到最右边然后从左往右扫把小于基准的都换到前面的区域。循环结束后再把基准换回i的位置这样i就是基准最终的落点。用频率值作为排序关键字数字本身无关紧要。3.3 完整代码与调用方式import random from collections import Counter def top_k_frequent(nums, k): counter Counter(nums) items list(counter.items()) # [[num, freq], ...] n len(items) target n - k # 第 n-k 小位置之后是最大的 k 个 left, right 0, n - 1 while True: pivot_idx partition(items, left, right) if pivot_idx target: break elif pivot_idx target: left pivot_idx 1 else: right pivot_idx - 1 return [num for num, _ in items[target:]] def partition(arr, left, right): idx random.randint(left, right) arr[idx], arr[right] arr[right], arr[idx] pivot arr[right][1] i left for j in range(left, right): if arr[j][1] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[right] arr[right], arr[i] return i需要注意快速选择是不稳定排序最终items[target:]里元素的相对顺序是乱的。但原题允许任意顺序返回所以没关系。如果面试官突然加条件“相同频率的元素按原数组出现顺序”这个解法就不合适你应该回头用堆加稳定排序或者调整比较逻辑。3.4 快速选择的适用条件与风险快速选择最大的优势是平均时间 O(N) 且不需要额外维护堆结构空间上只需要存一份频率数组。它在 N 很大的时候比堆解法有常数级的速度优势也更容易应付“海量内存中求 TopK”的纯内存场景。但它的缺点也很明显一是最坏情况是 O(N²)虽然随机化后概率极低二是它必须把全部数据一次性加载到内存里统计频率和构建数组。如果数据量大到内存放不下快速选择就无能为力了这时候堆方案因为可以流式处理反而更有优势。我见过不少人在面试时一上来就写快速选择结果分区函数写错或者边界条件判断反了最后调试了十分钟还没通过。我的建议是快速选择更适合作为第二方案展示技术深度而不是第一时间的默认打法。先把堆方案写出来保底再在追问中切到快速选择这一套组合下来面试官基本挑不出毛病。4. 解法三桶排序频率就是下标4.1 桶排序的适用场景第三种思路是桶排序。它有点像“空间换时间”的极致版适用条件是我们能预先知道频率的上限。在这个题目里任意数字的出现次数不会超过数组长度 N所以频率的取值范围是 1 到 N正好可以开一个长度为 N1 的桶数组。它的思想特别简单既然哈希表已经算出了每个数字的频率那我干脆建立一个“频率 - 数字列表”的映射。等你建完桶直接从最大频率往下扫扫到几个桶凑满 K 个元素就结束。4.2 代码实现反着扫桶from collections import Counter def top_k_frequent(nums, k): counter Counter(nums) max_freq max(counter.values()) if counter else 0 buckets [[] for _ in range(max_freq 1)] for num, freq in counter.items(): buckets[freq].append(num) result [] for freq in range(max_freq, 0, -1): for num in buckets[freq]: result.append(num) if len(result) k: return result return result这个实现有两个细节值得强调。第一桶数组的下标是从 0 到 max_freq。下标 0 永远不会有元素因为频率不可能为 0。所以扫描时直接从 max_freq 递减到 1 即可。第二buckets[freq].append(num)意味着相同频率的数字会自然聚在一个桶里。如果你需要“频率相同按数字大小返回”可以在最后对每个桶排序但那会让复杂度上升。原题不要求所以我选择保留原始顺序。4.3 三种解法复杂度对照表解法平均时间复杂度最坏时间复杂度空间复杂度稳定性适合场景哈希 最小堆O(N log K)O(N log K)O(N)可控数据量大、可流式处理快速选择O(N)O(N²)O(N)不稳定数据量适中、追求速度桶排序O(N)O(N)O(N)稳定值域或频率范围有限这个表基本涵盖了三者在面试中的定位堆解法最稳快速选择最快桶排序最优美。三者不是绝对优劣关系而是看数据形态和面试官问什么。我自己的经验是掌握前两种已经能应付绝大多数情况桶排序属于锦上添花。5. 代码之外的细节与坑5.1 堆元素该存值还是存频率这个问题我在 2.3 节已经提到一部分但值得单独再强调一次。核心原则是堆里什么信息都缺不了。如果只存频率不存数字那你最后根本不知道这些频率对应的元素是谁如果只存数字不存频率那你又没法在堆里比较大小。所以最小堆里存的必须是“数字 频率”的整体。在 Python 里最自然的写法是存元组(freq, num)因为元组天然支持按第一个元素、第二个元素依次比较。在 Java 里你可能要写比较器PriorityQueueint[] heap new PriorityQueue((a, b) - a[1] - b[1]);这里的int[]数组里放的是{num, freq}比较器只比较频率这一项。这个写法在面试白板上很常用也容易和面试官解释“我存的是一个 pair”。5.2 空数组、K越界、频率并列怎么处理空数组直接返回空列表。很多代码没考虑这一点Counter 会对空数组返回空字典这时候max(counter.values())会抛 ValueError。我的建议是在开头加一个if not nums: return []的守卫虽然题目可能用不到但养成习惯能救你很多次。K 越界K 比不重复元素个数还大。这种情况下理论上你是取不到的实际题目会保证合法但业务代码里一定要做截断。简单做法是k min(k, len(counter))。频率并列A 和 B 频率一样且 K 只够返回一个。原题不要求区分所以返回 A 或 B 都算正确。如果面试官要求按先后顺序你可以在桶排序里保持插入顺序或者在堆比较器上追加规则。但千万别在没被要求的情况下强行加排序那会白白增加复杂度。5.3 面试官追问数据流与分布式的 TopK这道题最经典的追问有两类。第一类如果数组变成无限数据流怎么办堆解法可以直接改造。维护一个固定大小为 K 的最小堆每来一个新数字更新频率计数器然后判断该数字现在的频率能否挤进堆里。由于计数是动态变化的这种场景下堆几乎是唯一合理的选择拉一条数据进来处理一次时间复杂度 O(log K)。第二类如果数据规模大到单机内存放不下怎么办这个时候要先想到分治把数据切分成多个分片每台机器统计自己分片里的 TopK最后合并各机器的结果再做一次全局 TopK。这其实是 MapReduce 思想的简化版。核心原则是“先局部去重统计再全局排序合并”。如果允许一定误差还可以用 Count-Min Sketch 这样的概率结构用很小的内存近似统计高频项但这是加分项不容易在面试现场完整写出来。5.4 从这道题迁移到真实业务场景在实际项目里这道题最常见的形态是“实时热搜榜”或“热门商品榜”。我做过一个某社区的热搜词统计系统当时的做法是将用户搜索行为写入消息队列并消费到日志表然后用定时任务把一天内的搜索记录聚合成“关键词 次数”的结构最后用最小堆取出 Top 100写入缓存供前端页面读取。这套流程其实就是在重复这道题的解法。但它有一个面试题里不会出现的麻烦频率不是静态的每隔几分钟就要刷新一次。如果每次都重新统计全量数据成本太高。这时候通常的做法是滑动窗口只统计最近半小时的行为配合窗口过期机制增量更新频率。所以你光会这道题的解法还不够还得在生产环境里考虑窗口、缓存、幂等这些附加问题。这也是为什么面试官喜欢拿这道题当引子追问各种工程化扩展的原因。6. 刷题心得与扩展练习建议6.1 类似题怎么举一反三前 K 个高频元素是一系列 TopK 题目的母题。你把它写透之后下面这些题基本都能顺手解决前 K 个高频单词把频率统计换成“单词 频率”排序规则多一个字典序。数组中的第 K 个最大元素立刻想到快速选择这题就是快速选择的最直接应用。根据字符出现频率排序直接用桶排序从高频到低频把字符拼出来。前 K 个最小元素堆比较器反过来用或者用最大堆去淘汰更大的元素。我的扩展练习建议是先做“数组中的第 K 个最大元素”它只需要快速选择不用哈希表适合单独练分区函数的手感。然后做“前 K 个高频单词”因为它多了一个字典序排序规则刚好能检验你对比较器的理解能不能处理复合条件。6.2 我的建议先默写最小堆再挑战快速选择最后说点我个人的刷题习惯。遇到这种“一题多解”的题我不会一上来就背最优解而是给自己定一个顺序第一遍只写暴力解也就是哈希表计数后按频率排序跑通题目。这个步骤的意义不是提交通过而是确认自己理解了问题模型。第二遍默写最小堆解法要求一次写对。因为这是面试中最常用的保底解法必须形成肌肉记忆。写完之后能清楚地讲出“为什么用最小堆而不是最大堆”才通过。第三遍在草稿纸上推快速选择的完整流程从选基准到退化成 O(N²) 的边界情况都想通。然后写代码自己构造一个最坏情况的数组测试一下观察随机化之后它不会真的退化。等这三遍走完你基本上可以在这道题上做到无论怎么追问都不慌默认解、优化解、场景解都有边界也心里有数。这道题我前前后后给不同的人讲过不下十次每一次讲完都会发现有人卡在同一个地方堆的容量和自我淘汰逻辑。如果你今天看完这篇能在草稿纸上把那句话写下来——“用最小堆保留最大的 K 个堆顶是最差的那个新人比最差强才配进来”这道题就算真正吃透了。剩下的事情就是在面试里把它稳稳写出来而已。