★ FEATURED ARTICLE 1. 题目拆解与面试官的真实意图1.1 “最小的k个数”到底在考什么这道题在面试题库里的出镜率高得离谱但很多人在刷题时只记住了解法没想明白它为什么值得被反复拿出来问。题目本身用一句话就能说清给定一个无序数组找出其中最小的 k 个数。但这句话背后藏了至少四个层次的考察点。第一层是基础coding能力。能不能写对一个能跑、不越界、不超时的解。第二层是数据结构敏感度。候选人能不能意识到堆、快速选择这类结构在处理“Top K问题”时的天然优势。第三层是复杂度分析能力。在不同数据规模下O(n log n) 排序、O(n log k) 堆、以及期望 O(n) 的快速选择各自的取舍是什么能不能讲清楚。第四层是工程思维。如果数组大到放不进内存、或者 k 非常小、或者数据是流式到达的该怎么办。网上很多题解一上来就甩代码但这道题的价值恰恰在于“为什么是它而不选别的”。如果只背代码换一个变体比如求中位数、求第 K 大、求出现频率最高的一批词照样不会做。先想清楚题目在问什么再动手写代码效率会高很多。1.2 读题时要主动确认的隐藏前提真实的面试场景里题目往往不是一次性给清楚的。很多人在牛客网、LeetCode 上刷惯了完整描述反而忽略了现场沟通这一步。对于“最小的k个数”动笔之前至少有三个点值得主动确认。第一个是 k 的范围k 是否可能等于 0是否可能等于数组长度。这两个边界看起来微不足道但写实现的时候影响很大。第二个是数组里有没有重复元素以及允许不允许结果乱序。有的面委会要求返回的结果按升序排列有的只说“返回最小的 k 个即可”这两者对算法的选择会产生直接影响。第三个是数据规模和内存限制。是十万个数的数组还是十亿个数是全部存在内存里还是只能读一遍。我见过不少候选人栽在这些“听起来很小”的问题上。比如没问清 k 是否合法直接排序然后 list[:k]k0 时能跑通k数组长度时也还好但万一 k 比数组长度还大呢报错还是截断不同处理方式反映出来的工程习惯差别很大。2. 从暴力解法到排序法的演进逻辑2.1 为什么先说“所有方案里最没技术含量”的解法拿到题目的第一反应大概率是排序取前 k 个。这完全正常而且从工程上说这未必是坏方案。排完序之后数组天然有序不仅能给你最小的 k 个还能给你最大的 k 个甚至能直接支持二分查找。一套排序后续所有查询需求都能满足这在很多业务系统里反而是优势。但面试题考察的侧重点不一样。排序算法的最优复杂度是 O(n log n)而这里只要求最小的 k 个数不要求整个数组有序。这意味着排序做了大量“额外的、你不关心的工作”——我们只关心最小的 k 个谁是老大其他元素内部谁大谁小对结果一点影响都没有。能不能把复杂度往下降就成了这道题真正的技术看点。所以我的建议是开头可以提一句排序解法作为理解和性能的基准线然后立刻转向堆和快速选择。不要一上来就堆优化也不要完全不提暴力法——不提会显得你没考虑过基础方案只提又显得缺乏优化意识。2.2 排序解法的一个常见误区有些人写排序解法时会写成这样def get_least_numbers(arr, k): arr.sort() return arr[:k]这在绝大多数编程语言里都没问题Python 的 TimSort 是稳定排序直接切片也快。但这个写法默认了一件事原数组可以被修改。在很多面试场景里面试官会追加一句“不能改变原数组顺序”这时候就必须拷贝一份再排否则你返回结果的同时把输入数据也弄坏了这是很严重的工程问题。拷贝的成本是 O(n) 的额外空间但在面试里这表现出你对“函数副作用”的敏感度。我在实际写业务代码时踩过类似的坑——对 DataFrame 做 inplace 排序或者对列表做 sort()结果后续流程依赖原来的顺序调试了半天才发现是前面的排序把数据改掉了。所以说哪怕是最简单的排序解法也值得养成“先想清楚能不能动输入数据”的习惯。3. 堆解法与 Top K 问题的经典组合3.1 为什么是“最大堆”而不是“最小堆”第二个主流解法是堆更准确地说是维护一个大小为 k 的最大堆。第一次接触的人很容易在这里卡住题目要“最小的 k 个”那我用小顶堆不是更直觉吗——把小顶堆的堆顶弹出来 k 次不就行了用小顶堆的思路确实成立但代价是堆的规模会膨胀到和整个数组一样大。你要先 O(n) 建一个完整的小顶堆然后连续弹出 k 次堆顶每次弹出的复杂度是 O(log n)总复杂度是 O(n k log n)。当 k 特别大的时候这个方案其实还行但问题在于空间你需要 O(n) 的堆来装下全部数字。最大堆的思路则完全反过来。我维护一个“只包含当前遇到的最小 k 个数”的容器容器的堆顶是这 k 个数里最大的那个。每来一个新数就把它和堆顶比一比如果它比堆顶小说明它比当前“前 k 小”里最大的那个还小那就把堆顶踢出去把它请进来如果它比堆顶大说明它连前 k 小都进不去直接扔掉。这个思路的巧妙之处在于我永远只需要一个规模为 k 的堆不管输入流多长内存占用都锁死在 O(k)。3.2 最大堆解法的完整代码与执行过程Python 的 heapq 模块只提供最小堆所以要实现最大堆一般有两种手段一是压入负值二是压入 ( -value, value ) 这样的元组。我比较推荐压负值代码最简洁也最容易跟面试官讲清楚。import heapq def get_least_numbers(arr, k): if k 0: return [] if k len(arr): return sorted(arr)[:k] max_heap [] for num in arr: if len(max_heap) k: heapq.heappush(max_heap, -num) else: # 当前元素比堆顶即最大的那个小才有替换价值 if num -max_heap[0]: heapq.heapreplace(max_heap, -num) return [-x for x in max_heap]注意这里heapreplace的用法它先弹出堆顶再压入新值整个过程只做一次 O(log k) 的调整。如果新数比堆顶还大连替换都不做这一步在数据量极大、k 又很小时能省下大量堆调整操作。我手动走一轮给你看。假设数组是[4, 5, 1, 6, 2, 7, 3, 8]k3。前三个数依次进堆此时堆里存的是[-5, -4, -1]对应的堆顶是 -5表示原值 5。遇到 1 时1 5替换堆变成原值[1, 4, 5]。遇到 66 5跳过。遇到 22 5替换掉 5堆变成[1, 2, 4]。遇到 7跳过。遇到 33 4替换堆变成[1, 2, 3]。最终结果就是[1, 2, 3]。看到没整个过程里堆里存的始终是“当前遇到的最小的 3 个数”而且因为我们存的是负数堆顶这个“最大值”在负值世界里反而是最小值敲代码的时候千万别绕晕了。3.3 堆解法的最强应用场景流式数据堆解法的一个独特优点是它天然适配“数据是流式到来”的场景。什么意思假设数组不是一次性全部给到你的而是一秒来一个、或者一天来一百万个而且你不知道总数有多少。这种情况下排序法和后面要讲的快速选择法全都失效了——因为快速选择需要随机访问整个数组排序需要全部数据在手而堆只关心当前的 k 个最小值来一个处理一个处理完就可以把前面的数据丢掉。用堆处理流式数据的时间复杂度是 O(n log k)其中 n 是数据总量。当 k 很小比如要找 top 10而 n 巨大比如十亿条日志时这个复杂度就非常友好。很多真实系统里的“实时排行榜”“高频词统计”都是这个套路。不过我也有个忠告如果 k 本身也很大比如 k 接近 n 的一半那么 O(n log k) 可能反而比直接排序的 O(n log n) 慢。因为 log k 和 log n 在 k 接近 n 时几乎相等但堆操作的常数因子往往比排序大。这个“k 越小越划算”的规律是选型时最重要的判断依据。4. 快速选择期望 O(n) 的高效解法4.1 从快速排序里抽出来的核心思想第三种解法是快速选择英文叫 Quickselect。它不像堆那样需要一个专门的数据结构而是直接借用了快速排序里单向划分partition的思想。回顾一下快排的核心动作挑选一个基准数pivot把数组重新排列让比基准数小的都跑到左边比基准数大的都跑到右边。这个动作做完基准数会落在它“排好序后应该待的位置”上。换句话说如果数组排好序第 i 个位置上是谁partition 做完之后基准数如果正好落在下标 k-1那基准数左边的所有数就全部小于它它们自然就是最小的 k-1 个数再加上基准数本身不就是最小的 k 个数了吗关键就在于这个“正好落在”。如果基准数落的位置小于 k-1说明最小的 k 个数都还在右边那一堆里那就只对右边继续做 partition左边全部忽略掉如果落的位置大于 k-1说明我们需要的结果在左边右边那一堆就可以直接丢掉。每一次递归都只处理一“半”另一“半”整个扔掉这正是它期望复杂度能压到 O(n) 的原因。4.2 快速选择的参考实现与边界处理import random def get_least_numbers(arr, k): if k 0: return [] if k len(arr): return sorted(arr)[:k] # 只对前 k 个位置做快速选择返回前 k 小的元素无序 def partition(left, right): pivot_idx random.randint(left, right) pivot_val arr[pivot_idx] arr[pivot_idx], arr[right] arr[right], arr[pivot_idx] store_idx left for i in range(left, right): if arr[i] pivot_val: arr[i], arr[store_idx] arr[store_idx], arr[i] store_idx 1 arr[store_idx], arr[right] arr[right], arr[store_idx] return store_idx left, right 0, len(arr) - 1 target k - 1 while left right: pos partition(left, right) if pos target: return arr[:k] elif pos target: left pos 1 else: right pos - 1写快速选择的时候有几个特别容易翻车的细节我逐个说。第一个是随机选基准数。如果不随机而是固定取区间第一个或者最后一个那么当数组本身有序时partition 退化得极其严重每一次都只能排除一个元素复杂度退化成 O(n²)直接超时。随机选一个基准数之后虽然理论上仍存在随机到最坏情况的可能但概率低到可以忽略这就是典型的“用随机化换稳健性”的思路。第二个是 partition 里对等于基准数情况的处理。上面代码里用的是arr[i] pivot_val才放到左边等于的情况会被归到右边去。好处是 partition 结束之后基准数左边都是严格小于它的右边是大于等于它的这样当有大量重复元素时我们能明确知道基准数的最终位置。如果改成会把等于基准数的全部堆积到左侧看起来没什么但这会让 partition 更加容易向右偏分区的平衡性变差在大量重复数据时性能可能退化。面试时提到这一点会比较加分。第三个是返回值是否需要排序。快速选择默认返回的结果是“无序的前 k 个数”因为它们只是被 partition 到了数组前 k 个位置内部并不有序。如果题目要求返回升序结果需要额外对 arr[:k] 再做一次排序排序成本是 O(k log k)——通常可接受。4.3 最坏情况为什么是 O(n²)以及如何补救跟堆解法和排序解法不同快速选择的复杂度分析要分情况讨论。期望 O(n)最坏 O(n²)。这中间的差距来自 partition 的不平衡性。假如每轮 partition 都很均匀数列大致被分成两半那么总工作量就是 n n/2 n/4 ... 2n也就是 O(n)。但假如运气极差每一轮选出来的基准数都是当前区间的最小值或最大值那么每次只能排除一个数总工作量变成 n (n-1) (n-2) ... n(n1)/2也就是 O(n²)。随机化已经把最坏情况出现的概率压得很低。但如果面试官进一步追问“有没有更稳定的解法”你可以提 BFPRT 算法也就是中位数对中位数。它的核心是精挑基准数——把数组按每五个一组分组每组取中位数再从这些中位数里递归取中位数作为基准数。这样做能保证每次 partition 至少排除掉固定比例的元素从而把最坏情况稳定在 O(n)。不过 BFPRT 的常数巨大工程上很少真的用它都是理论研究或者面试装逼用的我实际工作中从来没用过但知道它能显著提升你对这道题理解的系统性。5. 三种方案的对比矩阵与选型决策5.1 复杂度、空间、结果有序性的横向对比下面这个对比表是我在准备面试时常用来做总结的一张表几乎可以解决所有“到底用哪个”的疑问。方案时间复杂度额外空间是否修改原数组结果是否有序适合场景排序后取前 k 个O(n log n)O(1) 或 O(n)取决于是否允许修改是排序默认修改是k 较大、需要结果有序、代码简单优先最大堆大小为 kO(n log k)O(k)否否数据量大、k 较小、流式数据快速选择期望 O(n)、最坏 O(n²)O(1)原地或 O(log n)递归栈是否单次查询、数据量中等、对结果有序无要求这里有个细节快速选择的额外空间看起来是 O(1)但实际递归实现里栈的深度是 O(log n)所以严谨一点可以写成 O(log n)迭代实现则可以认为是 O(1) 辅助空间。面试时主动纠正这类小细节往往比背十道题更让面试官印象深刻。5.2 真实业务场景下我会怎么选说了半天理论如果在真实业务代码里让我选我的决策顺序是这样的。如果数据量不大比如几千条以内且代码要给别人维护直接排序取前 k 个。理由不是性能而是可读性。sorted(arr)[:k]一行代码谁都能看懂出 bug 的概率最低。几千条数据的排序耗时在毫秒级以下为了这点性能引入堆或者快速选择的复杂度得不偿失。如果数据是海量的比如千万级以上或者数据本身是持续流式到达的直接用堆解法。堆解法最大的优势就是不要求一次性拿到全部数据内存只涨到 k 就不涨了这在真实的大数据处理里几乎是决定性的。如果数据在内存里、量也不小、而且只需要一次性算一次那用快速选择。它能做到期望 O(n)比堆又要快一截。但要注意它和排序一样会动原数组不像堆解法无副作用。5.3 当 k 或 n 特别大时的工程改进思路还有一种常见变体我得提醒一句。如果 k 很大大到等于 n 的一半那维护一个大小为 n/2 的堆复杂度 O(n log(n/2))其实就是 O(n log n)这时候排序解法反而更简单。堆解法的优势区间在于 k 远小于 n比如 k100n十亿这时 log k 大约 7 次操作比 log n 的 30 次操作小得多计算量差距非常明显。如果数据是分布式的别自己写堆直接用 MapReduce 或 Spark 的思路先分片每个分片各自维护大小为 k 的局部堆最后归并时再从局部堆里整体选一遍。这也是“二阶段聚合”的思想我在处理日志 Top K 统计时经常这么干。这个点的价值在于面试者能借此表达自己“不仅有算法敏感度还有分布式系统的直觉”属于一个很自然的加分项。6. 实战经验测试用例设计与边界条件挖掘6.1 一组值得第一时间想到的测试用例很多人在面试时会写代码但不会测或者只测了 happy path。这道题想全覆盖下面这几组测试用例一个都不能少普通数组、k3[4,5,1,6,2,7,3,8]期望[1,2,3]k0任意数组期望返回空数组k1最小数存在多个时比如[0,0,1]结果应包含几个 0 要看题目怎么定义k 等于数组长度期望返回整个数组或数组的一份拷贝k 大于数组长度需要决定是报错还是截断包含大量重复值[2,2,2,2,2]任何 k 的取值都应该得到正确的数组已经升序排列的数组[1,2,3,4,5]这组主要用来测快速选择的退化问题已经降序排列的数组[5,4,3,2,1]包含负数[-3, -1, -5, 2, 0]负数排序的坑很多只有单个元素的数组对于 k 大于数组长度的情况不同题目的要求不一样但我在工程上更倾向于直接限制如果 k len(arr)抛出异常或者返回空而不是静默截断。静默截断会掩盖调用方的逻辑 bug这是我踩过坑后形成的习惯——有一个模块因为传进来的 k 偶尔大于数据长度被静默截断后返回了全集导致下游统计一度失真。6.2 我踩过的坑和复盘过程第一个坑是 Python 默认的 heapq 最小堆拿来求最小 k 个数直接 usage 会出大问题。我第一次写时想当然直接用 heapq结果堆顶永远是当前最小值新数跟堆顶比永远大于等于它导致堆越堆越大最后堆了 n 个元素效果和排序差不多还没有有序输出。后来才意识到要存负值把“最小堆”从功能上反转成“最大堆”。第二个坑是快速选择里 partition 用的基准数。我最早固定取 left结果遇到一个已经排好序的大数组直接打满超时警告。后来改成random.randint(left, right)之后同样的数据一秒之内跑完。这个教训让我养成了对“有序输入”这个 corner case 的高度敏感。第三个坑是结果顺序。有一次我在牛客网上提交快速选择版本的代码本地跑通提交后无论如何都判错。最后发现题目要求返回的结果必须升序排列但快速选择返回的结果是无序的。加一行arr[:k].sort()就过了。以后我拿到题第一件事就是确认输出顺序要求这个习惯帮我避免了很多不必要的返工。6.3 排查思路速查表现象可能原因排查手段k0 时返回错误没有提前处理 k0 边界在函数入口加 if k 0 分支堆解法结果含负数错误存负值后忘了解还原检查返回值是否使用了 -x快速选择超时没有随机选基准数改用 random.randint 选 pivot结果顺序不对题目要求有序输出确认需求再做一次 arr[:k].sort()原数组被意外修改排序或 partition 原地修改输入拷贝数组或在实现里注明副作用重复元素丢数partition 对、处理不当检查等号归属配合重复数组用例验证7. 变体扩展从这道题到更多高频题7.1 第 K 小的数、最大的 k 个数、中位数题目稍微改一个字解法思路完全不同这是面试里最常见的衍化方向。“第 k 小的数”和“最小的 k 个数”看着像但前者只关心落在第 k 位的那个值不需要把前 k-1 个全捞出来所以快速选择天然更适合一趟 partition 结束后若 pos k-1直接就返回 arr[pos]堆解法反而要维护整个大小为 k 的堆才能得到答案。“最大的 k 个数”其实就是对称问题把最大堆换成最小堆、或者把快速选择的比较方向反过来。有了这一题的底子这类变体基本不用重新想。“无序数组找中位数”等于求第 n/2 小的数本质还是快速选择。这也是为什么很多系统求中位数直接用一键算法而不开排序的原因。做大数据统计时中位数往往比均值更能反映分布形态但均值的计算必须排序级复杂度而中位数用快速选择只需要线性期望复杂度这个优势在数据量一大就显得特别关键。7.2 大数据与流式场景里的 Top K 变体最常见的工程变体是“词频 Top K”给定一篇超长文本或大量日志统计每个词出现的次数然后输出出现频率最高的 k 个词。这个场景通常拆成两步先用哈希表统计频率再把 (频率, 词) 这个二元组丢进大小为 k 的最小堆堆顶始终是当前最小的频率最后堆里留下的就是频次最高的 k 个。这个流程其实就是“哈希表计数 最小堆维护 Top K”在面试中出现的频率非常高。另一个高频变体是“有序数组求最小的 k 个数”——如果输入不是无序数组而是多个有序数组合并的结果那就变成多路归并问题核心是维护一个小顶堆用来在多个有序序列之间选当前最小的元素每次弹出之后再从对应序列取下一个。这个思路和懒加载、外排序有千丝万缕的联系。我在做外部排序时就用过类似思路——内存有限但多个增长的增量文件各自有序用小顶堆归并成全局有序输出。7.3 如果把数组换成多路有序链表这里再延伸一个让我印象深刻的问题给你 k 个升序链表合并成一个升序链表。看起来和“最小的 k 个数”无关但它的核心操作“从 k 个头节点里轮流取最小”正是我们前面用小顶堆维护 Top K 的直接应用——只不过堆里存的不再是数字而是 (节点值, 链表编号) 的元组。节点的 next 指针一旦移动堆里就少一个候选马上补一个进来。理解了这个连接再看“最小 k 个数”这道题就不再是孤立的知识点了。它和堆、快速选择、Top K、多路归并之间是互相关联的网络。刷题的意义不在于背题而在于把这种网络逐渐织密。8. 最后的个人心得应试与工程之间别丢了平衡先说考试侧。如果你正在准备面试我建议很明确优先吃透快速选择和堆这两种解法别只背代码要把“为什么这么选”讲明白。面试官想看的不是你会不会这道题而是你能不能在他追问到“如果 k 很大呢”“如果数据是流式的呢”“如果要求稳定排序呢”的时候依然给出合理的分析路径。我面过不少候选人代码写得又快又好但一问到复杂度推导就支支吾吾或者一追问“为什么堆要用最大堆而不是最小堆”就卡壳说明他只是在背方案没有真正理解内在逻辑。再说工程侧。真实业务里99% 的场景直接排序就够了堆和快速选择往往是“性能优化到了不得不用”的阶段才该引入的。特别要注意的是快速选择和堆都会引入结果无序的问题如果你的下游逻辑依赖有序数组这个影响常常被忽略直到线上出了诡异的数据排序 bug 才知道。写代码前先明确输出的使用方再决定要不要为了常数级的性能提升引入复杂度。我自己的做事习惯是所有涉及 Top K 的工具函数都先写一个“排序列”作为正确性基准再根据性能测试结果决定要不要上堆或快速选择。这样写出来的代码可读性好出问题的概率低也容易给其他人 review。如果绩效压力不大优先让代码给别人少添麻烦比多省那几毫秒重要得多。最后分享一个调试时的冷门小技巧在本地测试这道题时除了随机生成的普通数组、超大数组一定要加一组“所有元素全相同”的测试用例比如一万个 7。堆解法在大量重复元素时表现稳定快速选择则可能因为 partition 的等号处理方式不同出现结果偏斜。你只要跑过这一次基本就能立刻识别出自己写的 partition 在相等元素处理上的真实倾向这种对边界情况的敏感度是刷几十道题也换不来的。
阅读完成 · 觉得有帮助？
