两个正序数组的中位数：从归并到二分分割的完整解析

LeetCode 4 寻找两个正序数组的中位数这道题我刷了不止一遍每次以为理解了过阵子再看又发现新的理解盲区。尤其是那个时间复杂度要求——O(log(mn))——不知道卡住了多少人。今天索性把这题从暴力归并到二分分割的完整思路、边界条件和踩坑过程全部摊开写清楚。先说这题是什么给你两个已经排好序正序的数组长度分别是 m 和 n要求找出这两个数组合并后的中位数。这里的“合并”只是概念上的你不需要真的把两个数组拼起来。题目本身的输入输出很简单难点在于它要求的时间复杂度。如果你刚刷题不久看到 O(log(mn)) 大概率会犯难排好序的数组、中位数、log 级别的算法……这些词叠在一起很容易让人联想到二分查找。没错这题的正解就是一种变体的二分查找但它比在单个有序数组里二分要难得多难在边界条件的处理上。接下来我会按我自己的学习路径来拆解先实现一个完全正确的 O(mn) 归并解法当基线再推导 O(log(min(m,n))) 的二分分割法最后把那些让我在面试里差点翻车的边界细节全部列出来。1. 先看题它到底在考什么1.1 题目要求与本质理解两个正序数组比如nums1 [1,3]nums2 [2]合并后是[1,2,3]中位数就是 2。再比如nums1 [1,2]nums2 [3,4]合并后是[1,2,3,4]中位数是 (23)/2 2.5。这个理解起来没有任何问题。但记住题目原话要求时间复杂度是 O(log(mn))。这意味着你不能把两个数组真正合并因为合并一次的复杂度是 O(mn)直接违反题目的核心约束。所以这道题考察的本质是在不完整遍历所有元素的前提下利用两个数组各自有序的特性快速定位到“合并后中位数所在的位置”。还有一个容易忽略的点m 和 n 可能有一个为 0两个数组长度可能差得特别大比如一个长度为 1另一个长度为 10000。这些极端的输入会让边界条件瞬间暴露出来。很多解法在普通用例上跑得好好的一遇到空数组或者长度差悬殊就崩这也是这道题被评为 Hard 的重要原因之一。1.2 Hard 到底硬在哪我总结下来这道题的难度集中在三个地方。第一是思路的抽象性。大多数人的第一反应是“归并两个数组取中间”这个思路属于标准的线性思维在工程上完全正确但不是题目要的答案。要从“归并后取中位数”跳跃到“在两个数组上画分割线让分割线左边的所有元素都小于等于右边的所有元素”这一步抽象提炼不经过一定练习很难直接想到。第二是边界条件的繁琐。二分分割法需要在较短数组上做二分每次都要同时检查四个边界值nums1[i-1]、nums1[i]、nums2[j-1]、nums2[j]其中 i 和 j 还互相牵扯。任何一个越界、任何一个小等于号写错结果就完全不对。第三是奇偶长度的处理。两个数组总长度是奇数时中位数只有一个值偶数时是中间两个值的平均。这个在代码里要怎么统一处理而不是写两套分支也需要好好设计。面试时我见过不少人能口述二分思路但一上手写代码就卡在边界。所以我的建议是不要急着背代码先把“分割线”这套模型彻底在脑子里推演明白。1.3 两条路线难度天差地别面对这道题你实际上有两条路线可以走它们的取舍完全不同。路线一归并计数法。用双指针从头到尾比较两个数组的元素边走边计数走到中位数的位置附近就停下来。时间复杂度 O(mn)空间复杂度 O(1)思路零门槛代码十行以内能写完几乎不会出 bug。路线二二分分割法。在较短数组上二分枚举分割线的位置用交叉比较条件判断分割线是否合法最终在不合并数组的情况下直接算出中位数。时间复杂度 O(log(min(m,n)))这是题目期望的最优解也是面试官真正想看到的东西。这两条路线不是对立的。我在实际准备过程中先写好了归并计数法把它当成“标准答案生成器”再去实现二分分割法写完以后用随机生成的数组反复对拍验证两个结果一致。这样做的好处是二分法一旦写错你能快速定位是思路问题还是边界问题而不是对着一个错误答案干瞪眼。2. 基线解法归并思路的完整实现2.1 为什么先讲归并很多人觉得归并法太“低端”不屑于写。但我恰恰相反我认为归并法是这道题的“安全垫”。万一面试时脑子短路想不出二分分割法写一个高效的归并计数法也能拿不少分而且它实现起来极快不容易出错。还有一个作用它是二分分割法的完美对拍工具。你写完二分法之后怎么验证自己写对了用 LeetCode 自带的测试用例只是一部分。更可靠的方式是自己写一个循环随机生成大量测试数据把二分法的结果和归并法的结果比较。如果所有随机用例都一致你对代码的信心会强很多。不存储完整合并数组只做计数归并这种写法本身也是一种工程上常用的思路当数据量很大你不需要整个结果只需要某个特定位置的元素时完全可以用流式处理的方式一边遍历一边丢弃前面不需要的数据。这比“先排序再取中间值”的内存占用少得多。2.2 计数归并的代码我直接给出一个我常用的实现细节都写在注释里。def find_median_sorted_arrays(nums1, nums2): m, n len(nums1), len(nums2) total m n # 中位数涉及的两个位置统一按第几个元素从1开始计数 left_idx (total 1) // 2 right_idx (total 2) // 2 i j 0 count 0 left_val right_val 0 # 双指针归并但只记录目标位置附近的值 while i m and j n: if nums1[i] nums2[j]: cur nums1[i] i 1 else: cur nums2[j] j 1 count 1 if count left_idx: left_val cur if count right_idx: right_val cur break # 如果 nums1 或 nums2 还有剩余继续推进 while count right_idx and i m: cur nums1[i] i 1 count 1 if count left_idx: left_val cur if count right_idx: right_val cur while count right_idx and j n: cur nums2[j] j 1 count 1 if count left_idx: left_val cur if count right_idx: right_val cur return (left_val right_val) / 2.0这里有个设计我觉得很值得学习用left_idx和right_idx统一处理奇偶长度。当总长度是奇数时比如 7(71)//2 4(72)//2 4两个位置相同最终返回的实际上是同一个数的(cur cur) / 2.0 cur无损。当总长度是偶数时比如 8(81)//2 4(82)//2 5分别取第 4 和第 5 个数求平均正确。这个写法比“判断 total 是奇数还是偶数然后分别处理”要简洁得多。我后来在很多“取第 k 个位置”的题目里都复用了这个技巧。2.3 归并解法的局限归并法的优点很明显正确性直观代码简单空间 O(1)。但它的短板也致命时间复杂度 O(mn)。如果两个数组都特别大比如各有 100 万个元素那归并法就必须比较将近 200 万次而题目要求的 log 级别只需要几十次比较。这个差距在 LeetCode 的判定里体现得非常直接——如果卡死时间复杂度上限O(mn) 的代码很可能直接超时。就算不超时面试官也会追问怎么优化。必须理解为什么归并法做不到 log 级别因为它每一步只消耗掉两个数组当前指针指向的“较小元素”本质上是模拟整个排序过程的前半段。你取到第 k 个元素就必须至少进行 k 次比较。而二分法的核心洞察是我不需要按顺序逐个排除元素而是可以通过一次比较直接排除掉“一整半”的元素。这就是 log 和线性的本质区别。3. 核心思维中位数是一张“分割线”3.1 从“数”到“位置”的转化要理解二分分割法必须先理解一个非常重要的视角转换中位数不是一个固定的“元素”而是一个“分割位置”。拿一个简单的有序数组[1, 3, 5, 7, 9]举例。它的中位数是 5。我们换个角度把数组想象成被一条分割线切成左右两半左边是[1, 3]右边是[7, 9]5 刚好在分割线附近。对于奇数长度数组分割线正好穿过正中间的那个元素对于偶数长度数组分割线位于中间两个元素之间。现在推广到两个数组。我们假设把nums1和nums2在逻辑上合并成了一个有序数组然后在“中位数的位置”画一条分割线。因为两个数组各自有序合并后依然有序所以这条分割线会把合并数组分成左右两部分左边所有元素都小于等于右边所有元素。关键来了这条线在两个数组上的位置不是独立的。如果它在nums1左边取了 i 个元素在nums2左边取了 j 个元素而左边总共需要固定数量的元素那么 i 和 j 之间就有一个确定的换算关系。确定了 ij 就等于总左半元素数减 i。一句话总结中位数问题变成了“在较短数组上找到一个合适的分割位置 i使得合并后分割线左右两边满足有序性”。这就是整道题的灵魂。3.2 分割线两侧到底要满足什么条件假设在nums1中分割线左边的最后一个元素是nums1[i-1]分割线右边的第一个元素是nums1[i]。同理在nums2中对应的是nums2[j-1]和nums2[j]。要保证合并数组被正确切分必须满足两个跨数组的有序条件nums1[i-1] nums2[j]nums2[j-1] nums1[i]为什么只需要这两组因为每个数组内部本身就是有序的nums1[i-1] nums1[i]和nums2[j-1] nums2[j]自动成立。真正会出问题的是来自不同数组的左半元素和右半元素之间的交叉大小关系。一旦这两组条件都满足就可以保证分割线左边的所有元素不论来自哪个数组都小于等于分割线右边的所有元素。此时合并数组的全局有序性达成我们就能安心地取中位数了。具体来说如果总长度为奇数中位数就是max(nums1[i-1], nums2[j-1])也就是左半部分最大的那个数。如果总长度为偶数中位数是(max(nums1[i-1], nums2[j-1]) min(nums1[i], nums2[j])) / 2.0也就是左半最大和右半最小的平均。这两个公式看似简单但它们是整个算法的收敛目标所有二分动作都在为找到满足交叉条件的 i 服务。3.3 为什么只在小数组上二分有了分割线模型问题就变成怎么快速找到合法的 i一种直觉的方法是枚举。i 从 0 到 m 逐个试每次算出 j然后检查交叉条件。这确实能找到合法分割线但时间复杂度是 O(m)和归并法比没有任何优势仍然不满足题目要求。但是注意i 的取值有很强的单调性规律。当 i 增大时nums1[i-1]和nums1[i]会变大因为nums1是有序的而 j half - i 会变小所以nums2[j-1]和nums2[j]会变小。这个“一边变大、一边变小”的结构正好构成一个单调的分界点搜索问题天然适合二分。那为什么只在小数组上二分而不是在大数组上原因有两个。第一是复杂度更优在短数组上二分复杂度是 O(log(min(m,n)))在题目给出的数据范围下这比 O(log(max(m,n))) 更令人满意。第二是实现更简单因为 j 的值是 half - i当 i 的取值范围缩小时j 更不容易越界。如果选长数组做二分j 很容易超过 n 或小于 0边界条件处理起来要痛苦得多。所以实现时第一个动作就是如果len(nums1) len(nums2)就交换两个数组确保我们永远在短数组上二分。这个交换不会改变中位数只是让代码更好写。4. 最优解法二分分割法的完整实现4.1 参数准备与奇偶统一先把变量定义清楚。我们始终让nums1是较短数组长度 mnums2是较长数组长度 n。总长度total m n左半部分需要的元素数量half (total 1) // 2。这个 half 的取整方式很关键。(total 1) // 2等价于把中位数在奇数长度时归到左半部分。比如 total9half5左半部分有 5 个元素中位数就是左半部分第 5 个元素total10half5左半部分有 5 个元素中位数是左半第 5 个和右半第 1 个的平均。上面的设计把所有奇偶判断都统一到了同一套逻辑里。找分割线时我们永远只保证左半部分有 half 个元素至于最后是取一个值还是取平均值看 total 的奇偶性只在中位数计算的最后一步区分。变量left和right用来表示 i 的搜索范围。i 的合法取值范围是[0, m]对应nums1分割线左边元素的个数。当 i0 时nums1的所有元素都在右边当 im 时nums1的所有元素都在左边。记住这个含义后面边界条件都从它推导。4.2 四个边界值的处理每次二分取出一个候选的 i 后我们需要得到四个关键值。因为 i 和 j 都可能取到边界值导致某个元素不存在所以直接访问数组是危险的。最优雅的解决方式是引入无穷大和无穷小。nums1_left nums1[i-1] if i 0 else float(-inf) nums1_right nums1[i] if i m else float(inf) nums2_left nums2[j-1] if j 0 else float(-inf) nums2_right nums2[j] if j n else float(inf)我来解释一下为什么这样处理。当 i0 时nums1分割线左边没有任何元素nums1[i-1]不存在。此时我们在逻辑上把nums1_left视为负无穷大。负无穷大和任何数比较都能满足nums1_left nums2[j]也就是说这条边界自动合法。这是合理的分割线左边压根没有这个数组的元素自然不需要它参与“左边最大”的竞争也不会破坏右边的最小值条件。当 im 时同理nums1_right不存在把它视为正无穷大那么nums2_left nums1[i]也自动成立。这个技巧用一句废话解释就是不存在的边界不要给算法添乱。有了 -inf 和 inf四个边界值永远合法任何比较都不会越界报错所有分支逻辑得到极大简化。4.3 核心判断与完整代码有了四个边界值之后核心判断非常简单。我把判定逻辑总结成三种情况。第一种情况分割线合法nums1_left nums2_right且nums2_left nums1_right。此时直接按奇偶计算中位数返回结果。第二种情况nums1_left nums2_right。这说明nums1分割线左边的最大值太大了已经超过nums2分割线右边的最小值。要让分割线合法必须让nums1左边少拿一些元素也就是 i 要减小。因此执行right i - 1。第三种情况其余情况也就是nums2_left nums1_right。这说明nums2分割线左边的最大值太大了超过了nums1分割线右边的最小值。要让分割线合法必须让nums1左边多拿一些元素因为nums1左边元素变多时j会变小nums2左边元素变少nums2_left会变小。因此执行left i 1。我总结了一个记忆口诀“谁左边太大就往它的反方向缩。”如果nums1_left太大说明 i 撑得太大要左移如果nums2_left太大说明 i 太小、j 太大要右移。想清楚这个对应关系代码就不容易写错。完整代码def find_median_sorted_arrays(nums1, nums2): if len(nums1) len(nums2): nums1, nums2 nums2, nums1 m, n len(nums1), len(nums2) total m n half (total 1) // 2 left, right 0, m while left right: i (left right) // 2 j half - i nums1_left nums1[i-1] if i 0 else float(-inf) nums1_right nums1[i] if i m else float(inf) nums2_left nums2[j-1] if j 0 else float(-inf) nums2_right nums2[j] if j n else float(inf) if nums1_left nums2_right and nums2_left nums1_right: if total % 2 1: return float(max(nums1_left, nums2_left)) else: return (max(nums1_left, nums2_left) min(nums1_right, nums2_right)) / 2.0 elif nums1_left nums2_right: right i - 1 else: left i 1这段代码很短但每一处都有它的道理。比如while left right用的是小于等于不是小于。为什么因为当left right时可能仍然存在一个合法的 i 等着被验证如果用就会漏掉最后一次检查导致某些输入下直接返回空值。4.4 复杂度与正确性论证时间复杂度方面每次循环将搜索区间缩小一半而搜索区间是短数组的长度 m所以循环次数是 O(log m)。由于 m 是min(m, n)整体复杂度是 O(log(min(m,n)))这严格满足题目要求的 O(log(mn))——毕竟min(m,n)不超过(mn)/2所以log(min)不会比log(mn)差。空间复杂度是 O(1)只使用了几个整型和浮点型变量。关于正确性我在这里说一个便于面试时表述的论证思路。第一存在性合并后的有序数组在中位数的位置画一条线这条线天然满足交叉条件所以合法分割线一定存在。第二单调性i 增大时nums1_left和nums1_right都不减而j减小导致nums2_left和nums2_right都不增。所以如果当前 i 处nums1_left nums2_right那继续增大 i 只会让这个不等式更严重合法解必然在更小的 i 方向反之亦然。第三循环不会死循环每次迭代都会把left或right更新为mid 1或mid - 1区间长度严格递减。三点合起来可以证明二分搜索一定能收敛到合法分割线。5. 踩坑记录与调试心得5.1 最容易出现的三个 bug直接把这段代码丢给十个人我敢保证至少一半人会在前三种 bug 里面翻车而且翻车的姿势各不相同。第一个 bug数组越界。很多初学者拿到 j 就直接写nums2[j]和nums2[j-1]完全没有考虑 j 的取值范围。当 i 很小、j 很大时j可能等于 n访问nums2[j]就炸了当 i 很大、j 很小时j可能是 0nums2[j-1]也炸了。解决办法就是前面说的 -inf、inf 技巧把越界情况做逻辑上的“安全兜底”。第二个 bug死循环。二分最经典的问题是在区间长度为 2 时卡住。比如left0, right1此时mid0如果进入“需要增大 i”的分支我们执行left mid 1 1区间变成[1,1]下一次循环还能继续判断不会死循环。但如果错误地把更新写成left mid那当mid0时left仍然是 0区间永远停在[0,1]里出不来。所以务必记住二分更新的原则是排除 mid而不是保留 mid。第三个 bug中位数计算里的小数问题。有些语言里两个整数相除会直接截断。虽然我在 Python 示例里用了/ 2.0但在写其他语言时一定要确认除法行为。还有一个隐藏很深的坑max(nums1_left, nums2_left)里的两个值可能是 -infmin(nums1_right, nums2_right)里的值可能是 inf。如果在边界数组上错误地把不存在的值设成了 0 而不是 ±inf那么中位数结果就会莫名其妙地偏离正确答案而且测试用例越复杂越难排查。5.2 测试用例怎么设计刷这种边界条件密集的题绝对不能只靠 LeetCode 自带的示例数据。我自己的习惯是建一个本地测试脚本里面放上各种极端场景。这里给出一个让我曾经栽过跟头的测试清单场景示例输入期望结果考察点一个为空[]和[2,3]2.5j 的边界两个等长、完全不相交[1,2]和[3,4]2.5基本分割线完全相反[5,6]和[1,2]3.5交换数组后结果不变短数组在长数组内部[3]和[1,2,4,5]3.0i 为 0 或 m 的边界所有元素相同[1,1,1]和[1,1]1.0交叉条件的临界长度差极大[0,0]和[0,0,0,...,0]0.0half 较大时的表现负数参与[-5,-3]和[-2,-1]-2.5负数不干扰除了这些静态用例我特别推荐随机对拍。写一个简单的脚本循环生成各种长度的随机有序数组同时跑“归并计数法”和“二分分割法”把两者的结果做差比较。如果所有随机用例都通过你的信心会爆棚。这个对拍方法不仅在刷题时有用在面试前复盘时也会让你记得更牢。5.3 思路提炼与场景复用一道题刷完如果只是背住了代码那过一个月基本就忘了。我会刻意训练自己把解法压缩成一句话方便出现类似问题时快速联想。这题的“一句话模因”是两个有序数组的中位数等价于在短数组上找一个分割点使得交叉有序条件成立。以后遇到任何“两个排序数据源求分位数”“两道有序时间序列找共同阈值”这类问题我都会第一时间想到这条分割线模型。实际上我在工作中就遇到过类似的事。一次是要从两个不同平台返回的倒序排行榜中找出所有数据的“中间排名分数”。两个列表各自都有几十万条全部合并后再排序内存占用太大。最后我用的就是这种二分分割的思路在较短列表上二分直接算出了分位点。那一刻我真切体会到刷算法题的价值不在题目本身而在你在关键场景能想起哪种武器。6. 面试讲题时的一点体会最后说点面试场合的个人体会。这道题如果被问到我建议的讲解顺序是先用一句话说中位数的定义再把归并法的时间复杂度摆出来承认不足最后引出分割线模型。重点不是一上来就贴代码而是让面试官看到你是如何从 O(mn) 优化到 O(log) 的。面试官最在意的是边界条件的处理思路所以讲到二分时主动把“i0 时左边设 -inf”“im 时右边设 inf”这些设计说出来。这比默写代码更容易加分。还有一个细节交换短数组这一步最好在开头就声明“我们先确保在较短数组上二分这样复杂度更优且边界更安全”。这句话既能体现你的工程经验也能让后续代码的所有边界判断都变得好解释。我自己刷这题最大的感触就是真正难的不是那个二分框架而是那些“这里到底能不能取等号”“这个条件到底该用 elif 还是单独 if”的瞬间。把这些瞬间一个个想明白比刷十道新题都值。如果时间充裕我建议你尝试用其他语言重写一遍这个解法比如 Java 或 C因为不同语言在处理 -inf、inf、整数除法时的写法差异会逼着你更深入理解每一步的语义。亲手踩过几个边界坑之后你才算真正拿下了 LeetCode 4。