刷算法题的人十有八九会遇到这道“寻找两个正序数组的中位数”——第4题它在算法题库里的位置非常靠前几乎是二分查找的必修课。题面看起来简单到不行两个正序数组求合并后的中位数可复杂度偏偏要求 O(log(mn))直接把“先合并再排序”的念头摁死。这道题适合两类人一类是准备面试、想把二分边界练扎实的人另一类是卡在“为什么不能直接合并”“为什么排除一半就是安全的”这些坎上的初学者。看完这篇文章我不光给你能跑的代码更要把里面的门道拆开讲透。1. 题面理解与考点定位1.1 中位数这道题的隐藏前提先停下来读题。题目给的是两个“正序”数组这个前缀不是随手加的。中位数的定义大家都很熟合并后的总长度是奇数取中间那个数总长度是偶数取中间两个数的平均值。但真正决定这题难度的是“有序”这两个字。如果两个数组都是乱序的那唯一可靠的办法就是合并后重新排序绕不开 O(mn)。既然它们各自有序就说明有现成的排列信息可以复用我们可以通过局部比较不断收缩答案范围而不必真的把两个数组合成一个新数组。新手特别容易在这块掉坑题目说的是“合并后的中位数”于是第一反应就是先合并。合并本身就要遍历完两个数组哪怕用双指针归并也是 O(mn)题目不允许。换个角度想中位数不一定非要“合并之后”才能确定它完全可以被描述成一个排名问题——在两组有序数据的合集里找到第 k 小的元素。当总长是奇数时中位数就是第 total//21 小的数偶数时就是第 total//2 和第 total//21 小的两个数的平均。一旦做了这个转化题目就从“找一个特定值”变成了“找第 k 小”后面的思路全都可以围绕排名展开。1.2 复杂度要求传递的信号O(log(mn)) 这个复杂度等于把答案提前写在题面里了。想达到 log 级别唯一的正道就是每轮操作能排除掉大约一半的候选元素——这就是二分查找的思路。很多人的误区是以为这题是“在两个数组里二分”其实不是这里二分的是“候选元素集合的大小”。每次通过比较把确定不可能是答案的一段直接扔掉让剩余候选数量按指数级下降直到剩下最后一个。这里有个很直观的类比你想知道全班成绩排名第 10 的人是谁不需要真的把所有成绩列出来排一遍而是可以分组做擂台比较。每次找两组候选人里比较靠前的部分谁弱谁出局一轮就能淘汰掉一大批人几轮下来就能锁定目标。这个直觉就是整道题的核心。从复杂度倒推出算法方向也是面试官最想看到的能力——不是背模板而是能根据约束条件反推设计思路。方案时间复杂度空间复杂度适用场景合并后排序O((mn)log(mn))O(mn)无复杂度要求时双指针归并O(mn)O(1)要求线性复杂度时二分排除法O(log(mn))O(1)本题标准解法划分数组法O(log(min(m,n)))O(1)追求更严格复杂度时2. 核心思路从“合并找中位数”到“找第k小”2.1 中位数与第k小的关系解决这道题最容易理解的高效方法是“递归二分排除法”。思路一句话就能说清我们要找合并后的第 k 小数每次在两个数组的当前范围内各拿出前 k//2 个元素来比较谁那边的最后一个元素更小说明那一段里不可能存在第 k 小的数可以整块丢弃。反复做下去直到 k 变成 1答案就是当前两个数组头部的较小值。难点从来不是这句话而是“为什么可以这样丢”。这部分我会掰开讲。假设数组 A 的前 p 个元素整体上都不大于数组 B 的前 q 个元素pq k那么 A 的这 p 个元素一定不可能是第 k 小。道理很简单因为光 B 里就已经有 q 个元素排在它们前面了再加上 A 自己前面的 p-1 个元素它们最乐观也就排到第 pq-1 名也就是第 k-1 名永远摸不到第 k 名的位置。所以丢掉它们不会弄丢真正的答案。2.2 二分排除法的安全删除原则“安全删除”这四个字是整道题的基石值得反复咀嚼。具体到每次操作我们比较 A 和 B 的第 k//2 个元素谁更小就把谁所在数组的前 k//2 个元素全部丢掉。为什么假设 A 的第 k//2 个元素更小这意味着 A 的前 k//2 个元素全都小于等于 A 的第 k//2 个元素而 B 里至少有 k//2 个元素排在后面。那就至少存在 k//2 个来自 B 的元素比 A 的前 k//2 个元素都要大再加上 A 自身的前 k//2-1 个元素A 的前 k//2 个元素最多只能排到第 k-1 名。所以它们不可能是第 k 小可以直接出局。这个逻辑还有一个好处不必在乎两个数组元素的具体值到底怎么交错只要抓住“有足够多的元素确定排在它们前面”这一条删除就是安全的。面试时如果被问到“为什么排除一半不会丢掉中位数”你只需要把这个推理过程说清楚通常就能过关。这里我还想强调一个边界如果某个数组剩余长度不足 k//2那我们就只能取到它的最后一个元素。如果这个末尾元素依然更小那整个短数组都可以被排除此时第 k 小一定在长数组里反之如果短数组的末尾元素更大就说明长数组的前 k//2 个元素可以被排除。无论哪种情况都要保证“丢弃的元素个数”和“k 减少的个数”严格一致否则后面的下标会全部错乱。2.3 k值变化的数学逻辑写代码的人很容易在 k 的更新上犯错。核心原则一句话丢掉多少个元素k 就减多少。为什么因为第 k 小的定义建立在“当前所有剩余元素”的基础上一旦当前集合里少了 p 个元素原来的第 k 小就变成了剩余集合里的第 k-p 小。这就像排队打饭队伍前面走了 10 个人你从第 20 位自动变成第 10 位排名跟着前面人数同步收缩。理解这个对应关系后整个循环的结构就清晰了初始化 k 为中位数的排名每轮比较后排除掉较小一侧前 p 个元素同时令 k - p当 k 1 时答案就是当前两个数组头部元素里较小的那一个。这些逻辑写成代码一共也就七八行但想明白“为什么是第 k-p 小”而不是“第 k 小”才是真正吃透这道题的分水岭。很多人代码背得滚瓜烂熟一旦被追问 k 为什么变化就打结多半是这里没打通。3. 代码实现与逐段解析3.1 通用解法递归排除法直接上能跑的代码我用 Python 写逻辑和 C、Java 完全同构def find_median_sorted_arrays(nums1, nums2): def get_kth(k): m, n len(nums1), len(nums2) i, j 0, 0 while True: if i m: return nums2[j k - 1] if j n: return nums1[i k - 1] if k 1: return min(nums1[i], nums2[j]) half k // 2 ni min(i half, m) - 1 nj min(j half, n) - 1 if nums1[ni] nums2[nj]: k - ni - i 1 i ni 1 else: k - nj - j 1 j nj 1 total len(nums1) len(nums2) if total % 2 1: return get_kth(total // 2 1) else: return (get_kth(total // 2) get_kth(total // 2 1)) / 2这段代码的骨架是一个 while True 循环真正的出口只有三个某个数组被耗尽、k 已缩减到 1、或者在二者都不满足时继续排除。循环里做的事情非常单一找到两个数组当前的“第 half 个候选元素”越界就取末尾比较大小排除较小一侧的前面部分同步更新 i 或 j 以及 k。我建议你拿到代码后先不要背拿一组小例子手动走一遍比如 nums1[1,3,5,7,9]nums2[2,4,6,8,10]k 从 5 开始一步步看它是怎么排除的。很快你会发现自己已经能预判每一轮的排除方向那就说明思路真的进脑子了。3.2 边界条件分析写这段代码真正的硬仗在边界。我把最容易翻车的几个点拎出来i m 或 j n说明某个数组已经被全部排除不需要再比较答案直接在另一个数组的 jk-1 或 ik-1 下标处。k 1当前两个数组头部较小的一个就是答案直接返回 min(nums1[i], nums2[j])。ni 和 nj 的取值必须用 min(ihalf, m)-1 做截断保证不越界。哪怕 ni 取到了末尾排除的元素数量仍然按 ni-i1 计算。比较符号用 而不是 等于时优先排除 nums1 的前段这样不会漏答案也不会陷入死循环。这些细节看上去琐碎但几乎所有“逻辑看着对、提交就报错”的代码最后都折在这些地方。我的经验是别在纸上空想直接找一个奇数长度、一个偶数长度的真实用例手动跟一遍代码把 i、j、k 每一步的变化都写下来比看十篇解析都管用。3.3 复杂度与运行表现复杂度这块倒是很干净。每轮循环 k 至少减少 k//2而 k 的初始值最多是 total//21所以循环轮数是 O(log(mn)) 级别。每轮只有常数次比较和赋值总时间复杂度稳定在 O(log(mn))空间复杂度 O(1)。实际跑起来哪怕两个数组长度都到百万级也就二十多轮循环肉眼几乎感知不到耗时这就是 log 级别算法的体感。面试里如果追问“为什么不是 O(log(min(m,n)))”你可以补充说这是第 k 小模型的通用复杂度如果要严格依赖较短数组长度去优化就得换划分数组法了。4. 实操中会踩的坑4.1 奇偶情形最容易写错这题最高频的低级错误就是只处理奇数情况。不少同学写完直接 return get_kth((total1)//2)偶数长度的用例一跑就崩。更隐蔽的是即使你记得偶数要取平均也可能把两个 k 写错正确的是 total//2 和 total//21而不是 total//2-1 这种差一位的下标。判断奇偶用 total % 2 1奇数时中位数是第 total//21 个偶数时取第 total//2 个和第 total//21 个的平均。写完代码后建议用 [1,3] 和 [2,4] 这类小用例测一下立刻能暴露奇偶问题。这里我整理一个实用速查表收藏下来能省不少事错误类型现象原因分析正确做法奇偶未分离偶数长度样例失败中位数定义处理不完整偶数时取两个中间位置的平均k 的取值差一位结果偏移一个序号对第 k 小概念混淆奇数取 total//21偶数取 total//2 和 total//21数组越界崩溃运行时异常长度不足仍直接取 half用 min 限制下标越界取末尾递归切片拷贝性能明显退化每次都复制新数组用指针下标维护当前范围4.2 数组越界的经典诱因取第 k//2 个元素时如果数组长度不够直接写 nums1[ihalf] 必然会越界。这个问题在极端用例下几乎必然出现比如 nums1 只有 1 个元素nums2 有几百个元素此时 half 可能远大于 1 的长度不限制就崩。解法里用 ni min(ihalf, m)-1 做保护再配合“末尾元素也被纳入排除”这一逻辑就能把数组长度差距很大的情况处理干净。很多解法喜欢在某个数组长度不足时走特殊分支看起来像是在处理“短数组已经用完”其实本质都是同一个问题让索引安全落在有效范围内。4.3 另一种划分法到底该不该学除了第 k 小思路这题还有一种主流解法——在较短数组上二分划分点使两个数组的左侧元素总数恰好等于右侧再根据分割线附近的四个元素值决定中位数。这种划分法的复杂度可以做到严格的 O(log(min(m,n)))在追求极致性能的场景下更优。但以我的教学经验初学阶段不建议直接上手划分法它的边界比第 k 小更绕很多人写完根本解释不清“为什么左右两侧数量相等就能确定中位数”。建议先把第 k 小方法写熟能用 O(log(mn)) 解决并讲清楚原理对绝大多数面试场景已经完全够用。划分法等后续想深入时再研究能少走很多弯路。4.4 递归写法的坑栈溢出和重复计算很多人第一次实现时喜欢用递归也就是在 get_kth 里递归调用 get_kth(k-half)。单看递归深度只有 O(log k)一般不会爆栈但一旦在递归传参时用了切片比如 nums1[half:]复杂度立刻恶化。因为切片本身要拷贝数组每次递归都会复制一遍剩余元素空间和时间都变成 O(mn) 级别实测会慢一个数量级。正确做法是像上面的代码一样用 i 和 j 两个指针维护当前范围而不是真的去“切”数组。这也是我坚持用迭代实现的原因——不是递归不行而是递归版本一旦处理不好复杂度会悄悄变质。5. 延伸思考与面试策略5.1 同源变体题吃透这道题你会发现自己解锁了一串相关问题的通用解法。最直接的就是“在两个有序数组中找第 k 小”把本题的 get_kth 单独拎出来就是一道独立经典题。再往上还有“合并 K 个有序数组找中位数”多路归并场景通常用堆来维护每个数组的候选头部是另一个热门考点。更远的还有“数据流中找中位数”需要同时维护一个小顶堆和一个大顶堆动态保持两部分数量平衡。把这些题放到一起看能串成一条清晰的知识线有序结构上的排名查询问题解法无非是二分排除、堆维护、动态平衡这几类。理解了这题的模型等于给这条知识线开了一个好头。5.2 面试表达话术面试时怎么讲这道题顺序其实很关键。我推荐的表达结构是先说明为什么不能直接合并——因为 O(mn) 不满足题目约束再抛出第 k 小转化把中位数定义和 k 的选取一次说清然后讲每轮为什么能安全排除前 k//2 个元素用“至少有若干个元素一定排在它们前面”来证明最后补充边界情况比如某个数组被耗尽、k1 时怎么处理。这个顺序好处是层层递进面试官也容易跟着你的思路走。他们通常会在“安全删除”那里追问一次你只要把 2.2 节的推理复述一遍就能证明你是真理解而不是背答案。我见过不少候选人代码写得飞快但被问到“为什么排除一半不会丢掉中位数”就卡壳这个点值得提前练熟。5.3 实战后的个人建议最后聊点我实际刷题中的体会。这题我前前后后重写过很多次每次重写都会发现之前理解的漏洞最集中的就是“排除数量”和“k 递减数量”的一致性。后来我养成了一个习惯不管写哪道二分题都先写一个暴力版本做对拍。比如这题就直接写合并排序然后把二分版结果和暴力版结果放在几千组随机数组上比对一旦有不一致立刻就知道是边界逻辑出了问题。这种方式比对着单个用例死磕高效太多也非常适合用在其他算法题上。等你真正吃透了第 k 小模型再回头看这道“寻找两个正序数组的中位数”它就不再是背不下来的难题而是一个可以随手迁移的思维工具。