LeetCode 第4题“寻找两个正序数组的中位数”是我刷题路上卡得比较久的一道Hard题。它表面上是求中位数实际上考察的是对“有序数组二分”的深入理解两个正序数组长度分别为 m 和 n要求以 O(log(mn)) 的时间复杂度找出合并后的中位数。这个 log 限制是整道题的门槛也是面试官最看重的点。如果你正在刷 LeetCode 热门100题或者准备算法面试这道题值得花一整个晚上啃透。我写下这篇笔记把从暴力解到最优解的推导过程、边界条件的坑、面试追问都完整复盘一遍。1. 这道Hard题的三重门槛题目在考察什么1.1 读题时间复杂度限制是题眼题目描述简洁得有点误导性给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2请你找出并返回这两个正序数组的中位数。注意原题要求算法时间复杂度应该为 O(log(mn))。我第一次读题时注意力全在“中位数”三个字上完全忽略了复杂度限制。后来才发现这道题根本不是考你会不会求中位数——中位数的定义小学就学过——而是考你能否在 log 级别内完成两个有序数组的联合二分。这个限制直接排除掉所有先合并再求值的思路逼你把目光放到“结构复用”上。如果题目没有这个 log 限制那它顶多算一道简单题。加上这个限制它就变成了面试中区分度很高的一道题能写出 O(mn) 的人占多数能在面试现场稳定写出 O(log(min(m,n))) 的人则少很多。很多人误以为 Hard 题难在思路复杂实际上这道题难在“约束严格”你每一步优化都在跟复杂度较劲。1.2 第一反应解法为什么不合格大部分人的第一反应大概是这样的def findMedianSortedArrays(nums1, nums2): nums nums1 nums2 nums.sort() n len(nums) if n % 2 1: return nums[n // 2] return (nums[n // 2 - 1] nums[n // 2]) / 2这个写法刷测试用例完全没问题几分钟就能通过。但它有两个问题。第一每次都要把两个数组合并成一个新数组额外空间是 O(mn)第二排序是 O((mn) log(mn))即使换成双指针线性合并也只能做到 O(mn)距离题目的 log 要求还差一个量级。在面试中写出这种解法如果面试官只要求“做出来”那及时写出来并说明复杂度短板也算一种应急策略。但如果面试官明确要求满足题目复杂度那你就得继续往下优化。LeetCode 提交虽然只校验结果正确性不校验复杂度但你提交到讨论区看到别人 O(log) 的解法后很难不产生“我也要搞懂”的想法。1.3 测试用例带来的直觉分析这道题前先看几个典型用例它们能帮你建立直觉nums1 [1, 2], nums2 [3, 4]合并后是 [1, 2, 3, 4]中位数 2.5nums1 [1, 3], nums2 [2]合并后是 [1, 2, 3]中位数 2nums1 [], nums2 [1]中位数 1。第一个用例是偶数长度中位数取中间两个数的平均第二个是奇数长度中位数是正中间那个数第三个是空数组提醒你边界不能越界。观察发现中位数本质上就是把合并后的数组分成两半左半最大数和右半最小数决定了答案。这个“切分”视角是后面划分数组法的起点。到这里我总结出这道题的三重门槛第一重是能不能读懂 log 限制的潜台词第二重是从“合并思想”切换到“切分思想”第三重是处理奇偶、越界、空数组这些边界细节。接下来逐个击破。2. 双指针到第k小先拿到 O(log(mn)) 的解法2.1 归并式合并O(mn) 的边界感练习如果不想用 sort而是利用两个数组本身有序这个性质最朴素的做法就是双指针归并。类似归并排序的 merge 步骤用两个指针从头扫描每次比较当前元素大小把较小的放入合并结果直到数到中位数的位置。双指针归并比 sort 更“尊重题目条件”因为它真正利用了正序数组的性质。可惜它的复杂度仍然是线性的最坏情况下要扫描 (mn)//2 1 个元素时间复杂度 O(mn)。面试官看到这里一般会点头但紧接着就会问能不能更快这时候你应该意识到题目要求的 log 复杂度在二分族问题里是一个强烈的信号凡是看到 log都要想想能不能通过“每次排除一半”来加速。中位数的本质又是“第 k 小”的特例所以自然的想法是能不能直接找出合并后第 k 小的元素而不合并数组2.2 第 k 小的二分淘汰法复杂度踩到题目要求的边能。经典做法是利用“每次排除 k/2 个元素”的淘汰策略。把问题退化成“从两个有序数组中找第 k 小的元素”后我们比较 nums1[k//2 - 1] 和 nums2[k//2 - 1]这两个元素分别是两个数组的前 k//2 段中最后一个元素。如果 nums1[k//2 - 1] nums2[k//2 - 1]说明 nums1 的前 k//2 个元素都不可能是第 k 小直接把它们整体排除同时 k 减去排除的数量反之排除 nums2 的前 k//2 个。这个过程每次循环都把 k 缩减一半所以总复杂度是 O(log(mn))。当某个数组提前用完时直接用另一个数组下标加 k 得出答案。每次淘汰时如果 k//2 超出数组剩余长度要用 min 保护不然会越界。下面给出我写的第 k 小版本def findMedianSortedArrays(nums1, nums2): m, n len(nums1), len(nums2) def get_kth(k): idx1, idx2 0, 0 while True: if idx1 m: return nums2[idx2 k - 1] if idx2 n: return nums1[idx1 k - 1] if k 1: return min(nums1[idx1], nums2[idx2]) half k // 2 new_idx1 min(idx1 half, m) - 1 new_idx2 min(idx2 half, n) - 1 if nums1[new_idx1] nums2[new_idx2]: k - new_idx1 - idx1 1 idx1 new_idx1 1 else: k - new_idx2 - idx2 1 idx2 new_idx2 1 total m n if total % 2 1: return get_kth((total 1) // 2) return (get_kth(total // 2) get_kth(total // 2 1)) / 2用生活类比的话这就像两本已经按页码排好序的字典你想快速找到第 k 个词条。你不必一页页翻而是每次各翻一半哪边的“当前半段末尾”更小就把那边的半段扔掉继续在剩余部分里找第 k - half 小。翻的次数就是 log 级别。2.3 第k小距离最优解还差在哪这个解法已经满足题目的 O(log(mn)) 要求面试中写出来是合格的。但如果继续深究会发现有个地方还能优化二分淘汰的对象是两个数组的总长度复杂度是 O(log(mn))而划分数组法可以把二分对象锁定在较短数组上达到 O(log(min(m,n)))。当 m 和 n 的量级相差很大时区别就出来了。比如 nums1 长度是 1 万nums2 长度是 1000 万log(mn) 和 log(min(m,n)) 的差距差不多是 4 倍左右的循环次数。虽然常数差异不大但 LeetCode 官方题解的主角是后者面试官如果追问“还有没有更优的解法”答案也是这个方向。到这里我们已经有了一条清晰的演进路线O((mn)log(mn)) → O(mn) → O(log(mn)) → O(log(min(m,n)))。接下来详细拆解最后一步的思路和实现。3. 划分数组法的核心推导为什么必须在短数组上二分3.1 一刀切两半的直觉中位线必然同时穿过两个数组想象一下把合并后的虚拟数组从正中间切一刀切完后左半部分有 total_left 个元素右半部分有剩下的元素。分割线是竖直的但因为原数组是两个这条分割线其实由两个数组上各自的一个“切点”组成在 nums1 上切在 i 位置左边有 i 个元素在 nums2 上切在 j 位置左边有 j 个元素。中位数的判定条件就变成左半部分的所有元素都小于等于右半部分的所有元素且左右两半数量相等偶数时或左半多一个奇数时。由于两个数组各自有序这个全局条件可以化简为两个局部条件nums1[i-1] nums2[j]nums1 左侧最大值不超过 nums2 右侧最小值nums2[j-1] nums1[i]nums2 左侧最大值不超过 nums1 右侧最小值。只要这两个条件同时成立整个左半都 整个右半。这是划分数组法全部逻辑的基石你可以在草稿纸上画几条竖线验证一下nums1 的前 i 个和 nums2 的前 j 个合成左半其余合成右半任何跨数组的相邻元素对都在这两个条件里覆盖到了。3.2 i 和 j 的绑定关系枚举一个另一个自动确定中位数的定义要求左半元素个数固定。总数 total m n 时左半元素个数取 total_left (m n 1) // 2。为什么是加 1因为整数除法在 total 为奇数时会让左半多一个元素total3 时 total_left2左半多 1中位数正好是左半最大值total4 时 total_left2左右相等中位数是左半最大值和右半最小值的平均。于是 i 和 j 被唯一绑定i j total_left即 j total_left - i。我们只需要在一个数组上枚举 i另一个数组的切点就自动确定了。这里的自由度被消掉一个。那在哪个数组上枚举答案是在较短的数组上。原因很实在i 的合法范围是 [0, m]而 j 的合法范围是 [0, n]。如果 m n那枚举 i 时算出的 j 很可能会超出 [0, n]要么小于 0 要么大于 n直接导致越界访问。反过来如果保证 m n那么 j total_left - i 在 i 取 [0, m] 时一定落在 [0, n] 内。所以第一步永远先交换让短的数组做二分搜索的目标。3.3 如何判断 i 偏大还是偏小现在问题变成在 [0, m] 内二分查找合适的 i。每次取 mid 作为 i算出 j检查两个交叉条件。麻烦在于两个条件可能一个成立一个不成立如何决定往左还是往右搜方向判断的核心只有两条如果 nums1[i-1] nums2[j]说明左半里 nums1 的元素多了i 应当减小如果 nums2[j-1] nums1[i]说明左半里 nums2 的元素多了i 应当增大。注意讨论 nums1[i-1] 和 nums2[j-1] 时天然要求 i 0 和 j 0同时 nums1[i] 和 nums2[j] 也要求 i m 和 j n。这些边界之后统一用正负无穷处理先把方向搞清楚。直觉上可以这样理解你在两根长度不等的绳子上同时找切口要求切口左边总长固定。先猜一个位置如果发现左边某一段里有元素比右边还大说明这一侧切多了就往回收一点反之说明切少了就往外放一点。二分就是不断对“多了还是少了”做调整最终收敛到唯一正确位置。3.4 手工推演两个用例奇数和偶数路径先用奇数用例。nums1 [2]nums2 [1, 3]。此时 m1, n2已经是 m ntotal3total_left2。二分范围 [0, 1]取 i0j2。四个极值是a_left_max -INFa_right_min 2b_left_max 3b_right_min INF。检查a_left_max b_right_min不可能b_left_max a_right_min3 2成立说明 i 太小左边界变为 1。再取 i1j1。a_left_max2a_right_minINFb_left_max1b_right_min3。两个交叉条件都成立找到答案。total 为奇数直接返回 max(2, 1) 2。再用偶数用例。nums1 [1, 2]nums2 [3, 4]。m2, n2total4total_left2。取 i1j1。a_left_max1a_right_min2b_left_max3b_right_min4。第二个条件 b_left_max a_right_min3 2成立说明 i 太小左边界变为 2。取 i2j0。a_left_max2a_right_minINFb_left_max-INFb_right_min3。条件都不成立命中。total 为偶数返回 (max(2, -INF) min(INF, 3)) / 2 2.5。这两个用例覆盖了奇偶两条路径也顺带验证了交换数组后的处理逻辑。你会发现整个二分过程每次只根据一个比较结果移动边界和普通二分查找没有任何区别关键是搞清楚往哪个方向移动。4. 完整代码与边界条件index越界和奇偶陷阱复盘4.1 可直接运行的 Python3 主版本把上面的推导落成代码完整版本如下class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float: m, n len(nums1), len(nums2) if m n: nums1, nums2 nums2, nums1 m, n n, m total_left (m n 1) // 2 left, right 0, m INF float(inf) while left right: i (left right) // 2 j total_left - i a_left_max -INF if i 0 else nums1[i - 1] a_right_min INF if i m else nums1[i] b_left_max -INF if j 0 else nums2[j - 1] b_right_min INF if j n else nums2[j] if a_left_max b_right_min: right i - 1 elif b_left_max a_right_min: left i 1 else: if (m n) % 2 1: return max(a_left_max, b_left_max) return (max(a_left_max, b_left_max) min(a_right_min, b_right_min)) / 2 return 0.0代码很短但每一行都有讲究。交换数组是为了保证 m n避免二分过程中 j 越界total_left 是左半元素数量四个 INF 赋值把边界情况变成普通情况。while 循环用 left right 的模板命中后直接返回不会出现死循环。4.2 四个 INF 边界值的作用i 0 时nums1 左侧一个元素都没有a_left_max 理应是“没有”但为了统一计算 max把它设成 -INF任何正常值都比它大它永远不会成为左半最大值。i m 时nums1 右侧没有元素a_right_min 设成 INF任何正常值都比它小它永远不会成为右半最小值。nums2 的边界同理。不这样处理的话你得写四五层判断去讨论 i 或 j 到达边界时哪些元素不存在。用 INF 之后边界元素自动被“架空”四个比较和最后的 max/min 计算全部照常进行。这是我在代码里最想强调的小技巧它比每个分支写 if 判断要清晰得多也不容易漏。提示手推这道题时建议把 -INF 和 INF 直接写成负无穷和正无穷别用具体大数比如 -10**9因为测试数据里可能出现更大的负数。4.3 我踩过的三个坑每一条都是真实报错第一个坑是忘记交换数组。我第一次写的时候直接在长数组上二分拿 nums1[1,3,5]、nums2[2] 测试m3, n1total_left2。二分取 i0 时 j2但 nums2 长度只有 1访问 nums2[j] 直接 IndexError。交换成短数组后j 的取值范围被约束在 [0,n] 内这类越界在结构上就不存在了。第二个坑是 total_left 写成了 (m n) // 2。偶数长度时没问题奇数长度时左半少了一个元素中位数直接错。比如 [1,3] 和 [2]正确中位数是 2写成 (mn)//2 后会得到 1.5。核心记忆点是total_left 永远用加一再整除保证奇数时左半多一个。第三个坑是二分循环条件用 left right结果在部分用例上死循环或找不到答案。因为 i 的搜索空间是闭区间 [0, m]命中条件需要比较到 left right 时的那一格用 left right 会漏掉。我后来统一用 left right命中后立即返回这个坑就再没踩过。注意记忆 total_left 时可以把它理解为“左侧比右侧多一个奇数时或相等偶数时”加一再整除是唯一正确写法。4.4 空数组和单元素数组验证空数组和单元素数组是最容易写崩的边界。比如 nums1 [], nums2 [1]。交换后依然 m0, n1total_left 1。循环只可能取 i0j1。此时 a_left_max -INFa_right_min INF因为 i m 成立b_left_max 1b_right_min INF。a_left_max b_right_min不成立b_left_max a_right_min不成立。直接命中奇数返回 max(-INF, 1) 1。再比如两个数组都有元素但其中一个较短nums1 [1], nums2 [2, 3, 4, 5]。m1, n4total5total_left3。二分 i 只有 0 或 1 两种可能无论哪种j 都不会越界。这类用例我建议你在本地多跑几组把奇偶、空数组、等长数组、差一个长度的数组全都覆盖一遍边界条件才能真正算过关。5. 复杂度对比与面试追问把这道题当作系统设计题来准备5.1 三种解法的复杂度对照给出一张表解法时间复杂度空间复杂度说明合并后排序O((mn) log(mn))O(mn)最简单但不利用有序性双指针归并O(mn)O(1)利用有序性仍在线性级别第 k 小淘汰O(log(mn))O(1)满足题目要求思路直观划分数组二分O(log(min(m,n)))O(1)最优解二分在短数组上面试时先把这张表在脑子里过一遍然后根据面试官要求决定讲多深。如果时间只剩十分钟直接写第 k 小版本是务实选择代码更快不容易出错如果面试官明显在考察你对二分的理解那划分数组法才是完整答案。5.2 换到 Java 或 C 时要注意的差异Python 里 (mn1)//2 没有类型风险但 Java 和 C 里要小心运算符和类型转换。我在写 Java 版本时习惯这样处理边界值int i (left right) 1; int j totalLeft - i; int aLeftMax (i 0) ? Integer.MIN_VALUE : nums1[i - 1]; int aRightMin (i m) ? Integer.MAX_VALUE : nums1[i];用 Integer.MIN_VALUE 和 Integer.MAX_VALUE 代替正负无穷返回结果时再转 double。注意 total_left 用 (m n 1) 1 时要加括号右移运算符优先级低于加法漏掉括号会算出完全错误的结果。C 里返回偶数中位数时 (max min) / 2.0 要带小数点写成 / 2 就是整数除法直接截断。5.3 面试官可能的追问与回答思路我总结了三个大概率被追问的点。第一“为什么只用两个交叉条件就能保证整个左半都小于右半”回答要点两个数组各自有序左半内部已有序右半内部已有序只需检查跨数组的相邻边界即 nums1 左侧最大值与 nums2 右侧最小值、nums2 左侧最大值与 nums1 右侧最小值。第二“如果数组里有重复元素条件还能用吗”回答能。条件里用的是 或 重复元素不会破坏划分有效性。比如 nums1[1,1,1], nums2[1,1]按公式枚举 i 依然能找到满足交叉条件的切点最终返回 1。第三“如果扩展到 k 个有序数组找中位数怎么做”回答可以用大小为 k 的堆维护每个数组当前指针指向的最小值逐次弹出到中位位置复杂度是 O(总元素数 * log k)也可以两两合并面试中通常只需要讲思路。这道题单拎出来的意义是让你掌握“两个数组上同时二分”的思想扩展到多数组时主要套递归和分治套路。我在面试中吃过一次亏当时只说了第 k 小解法面试官追问“能不能在短数组上二分”时我卡住了。后来我把这道题当成一次系统设计题来准备——先明确约束再画切分模型再推边界最后落到代码——这套流程对其他二分题目同样适用。最后分享一个我自己的刷题体会。这道题我一共刷了三轮第一轮看题解似懂非懂第二轮自己手推了二十组用例第三轮才能做到十分钟内无 bug 写出最优解。中位数这类题不怕慢怕的是背代码。建议你在看代码前先在草稿纸上画出两个数组和切点每次二分都标注 i、j、四个极值推完三个用例后再写代码那才是真正掌握了。
LeetCode第4题：二分查找两个正序数组的中位数最优解
LeetCode 第4题“寻找两个正序数组的中位数”是我刷题路上卡得比较久的一道Hard题。它表面上是求中位数实际上考察的是对“有序数组二分”的深入理解两个正序数组长度分别为 m 和 n要求以 O(log(mn)) 的时间复杂度找出合并后的中位数。这个 log 限制是整道题的门槛也是面试官最看重的点。如果你正在刷 LeetCode 热门100题或者准备算法面试这道题值得花一整个晚上啃透。我写下这篇笔记把从暴力解到最优解的推导过程、边界条件的坑、面试追问都完整复盘一遍。1. 这道Hard题的三重门槛题目在考察什么1.1 读题时间复杂度限制是题眼题目描述简洁得有点误导性给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2请你找出并返回这两个正序数组的中位数。注意原题要求算法时间复杂度应该为 O(log(mn))。我第一次读题时注意力全在“中位数”三个字上完全忽略了复杂度限制。后来才发现这道题根本不是考你会不会求中位数——中位数的定义小学就学过——而是考你能否在 log 级别内完成两个有序数组的联合二分。这个限制直接排除掉所有先合并再求值的思路逼你把目光放到“结构复用”上。如果题目没有这个 log 限制那它顶多算一道简单题。加上这个限制它就变成了面试中区分度很高的一道题能写出 O(mn) 的人占多数能在面试现场稳定写出 O(log(min(m,n))) 的人则少很多。很多人误以为 Hard 题难在思路复杂实际上这道题难在“约束严格”你每一步优化都在跟复杂度较劲。1.2 第一反应解法为什么不合格大部分人的第一反应大概是这样的def findMedianSortedArrays(nums1, nums2): nums nums1 nums2 nums.sort() n len(nums) if n % 2 1: return nums[n // 2] return (nums[n // 2 - 1] nums[n // 2]) / 2这个写法刷测试用例完全没问题几分钟就能通过。但它有两个问题。第一每次都要把两个数组合并成一个新数组额外空间是 O(mn)第二排序是 O((mn) log(mn))即使换成双指针线性合并也只能做到 O(mn)距离题目的 log 要求还差一个量级。在面试中写出这种解法如果面试官只要求“做出来”那及时写出来并说明复杂度短板也算一种应急策略。但如果面试官明确要求满足题目复杂度那你就得继续往下优化。LeetCode 提交虽然只校验结果正确性不校验复杂度但你提交到讨论区看到别人 O(log) 的解法后很难不产生“我也要搞懂”的想法。1.3 测试用例带来的直觉分析这道题前先看几个典型用例它们能帮你建立直觉nums1 [1, 2], nums2 [3, 4]合并后是 [1, 2, 3, 4]中位数 2.5nums1 [1, 3], nums2 [2]合并后是 [1, 2, 3]中位数 2nums1 [], nums2 [1]中位数 1。第一个用例是偶数长度中位数取中间两个数的平均第二个是奇数长度中位数是正中间那个数第三个是空数组提醒你边界不能越界。观察发现中位数本质上就是把合并后的数组分成两半左半最大数和右半最小数决定了答案。这个“切分”视角是后面划分数组法的起点。到这里我总结出这道题的三重门槛第一重是能不能读懂 log 限制的潜台词第二重是从“合并思想”切换到“切分思想”第三重是处理奇偶、越界、空数组这些边界细节。接下来逐个击破。2. 双指针到第k小先拿到 O(log(mn)) 的解法2.1 归并式合并O(mn) 的边界感练习如果不想用 sort而是利用两个数组本身有序这个性质最朴素的做法就是双指针归并。类似归并排序的 merge 步骤用两个指针从头扫描每次比较当前元素大小把较小的放入合并结果直到数到中位数的位置。双指针归并比 sort 更“尊重题目条件”因为它真正利用了正序数组的性质。可惜它的复杂度仍然是线性的最坏情况下要扫描 (mn)//2 1 个元素时间复杂度 O(mn)。面试官看到这里一般会点头但紧接着就会问能不能更快这时候你应该意识到题目要求的 log 复杂度在二分族问题里是一个强烈的信号凡是看到 log都要想想能不能通过“每次排除一半”来加速。中位数的本质又是“第 k 小”的特例所以自然的想法是能不能直接找出合并后第 k 小的元素而不合并数组2.2 第 k 小的二分淘汰法复杂度踩到题目要求的边能。经典做法是利用“每次排除 k/2 个元素”的淘汰策略。把问题退化成“从两个有序数组中找第 k 小的元素”后我们比较 nums1[k//2 - 1] 和 nums2[k//2 - 1]这两个元素分别是两个数组的前 k//2 段中最后一个元素。如果 nums1[k//2 - 1] nums2[k//2 - 1]说明 nums1 的前 k//2 个元素都不可能是第 k 小直接把它们整体排除同时 k 减去排除的数量反之排除 nums2 的前 k//2 个。这个过程每次循环都把 k 缩减一半所以总复杂度是 O(log(mn))。当某个数组提前用完时直接用另一个数组下标加 k 得出答案。每次淘汰时如果 k//2 超出数组剩余长度要用 min 保护不然会越界。下面给出我写的第 k 小版本def findMedianSortedArrays(nums1, nums2): m, n len(nums1), len(nums2) def get_kth(k): idx1, idx2 0, 0 while True: if idx1 m: return nums2[idx2 k - 1] if idx2 n: return nums1[idx1 k - 1] if k 1: return min(nums1[idx1], nums2[idx2]) half k // 2 new_idx1 min(idx1 half, m) - 1 new_idx2 min(idx2 half, n) - 1 if nums1[new_idx1] nums2[new_idx2]: k - new_idx1 - idx1 1 idx1 new_idx1 1 else: k - new_idx2 - idx2 1 idx2 new_idx2 1 total m n if total % 2 1: return get_kth((total 1) // 2) return (get_kth(total // 2) get_kth(total // 2 1)) / 2用生活类比的话这就像两本已经按页码排好序的字典你想快速找到第 k 个词条。你不必一页页翻而是每次各翻一半哪边的“当前半段末尾”更小就把那边的半段扔掉继续在剩余部分里找第 k - half 小。翻的次数就是 log 级别。2.3 第k小距离最优解还差在哪这个解法已经满足题目的 O(log(mn)) 要求面试中写出来是合格的。但如果继续深究会发现有个地方还能优化二分淘汰的对象是两个数组的总长度复杂度是 O(log(mn))而划分数组法可以把二分对象锁定在较短数组上达到 O(log(min(m,n)))。当 m 和 n 的量级相差很大时区别就出来了。比如 nums1 长度是 1 万nums2 长度是 1000 万log(mn) 和 log(min(m,n)) 的差距差不多是 4 倍左右的循环次数。虽然常数差异不大但 LeetCode 官方题解的主角是后者面试官如果追问“还有没有更优的解法”答案也是这个方向。到这里我们已经有了一条清晰的演进路线O((mn)log(mn)) → O(mn) → O(log(mn)) → O(log(min(m,n)))。接下来详细拆解最后一步的思路和实现。3. 划分数组法的核心推导为什么必须在短数组上二分3.1 一刀切两半的直觉中位线必然同时穿过两个数组想象一下把合并后的虚拟数组从正中间切一刀切完后左半部分有 total_left 个元素右半部分有剩下的元素。分割线是竖直的但因为原数组是两个这条分割线其实由两个数组上各自的一个“切点”组成在 nums1 上切在 i 位置左边有 i 个元素在 nums2 上切在 j 位置左边有 j 个元素。中位数的判定条件就变成左半部分的所有元素都小于等于右半部分的所有元素且左右两半数量相等偶数时或左半多一个奇数时。由于两个数组各自有序这个全局条件可以化简为两个局部条件nums1[i-1] nums2[j]nums1 左侧最大值不超过 nums2 右侧最小值nums2[j-1] nums1[i]nums2 左侧最大值不超过 nums1 右侧最小值。只要这两个条件同时成立整个左半都 整个右半。这是划分数组法全部逻辑的基石你可以在草稿纸上画几条竖线验证一下nums1 的前 i 个和 nums2 的前 j 个合成左半其余合成右半任何跨数组的相邻元素对都在这两个条件里覆盖到了。3.2 i 和 j 的绑定关系枚举一个另一个自动确定中位数的定义要求左半元素个数固定。总数 total m n 时左半元素个数取 total_left (m n 1) // 2。为什么是加 1因为整数除法在 total 为奇数时会让左半多一个元素total3 时 total_left2左半多 1中位数正好是左半最大值total4 时 total_left2左右相等中位数是左半最大值和右半最小值的平均。于是 i 和 j 被唯一绑定i j total_left即 j total_left - i。我们只需要在一个数组上枚举 i另一个数组的切点就自动确定了。这里的自由度被消掉一个。那在哪个数组上枚举答案是在较短的数组上。原因很实在i 的合法范围是 [0, m]而 j 的合法范围是 [0, n]。如果 m n那枚举 i 时算出的 j 很可能会超出 [0, n]要么小于 0 要么大于 n直接导致越界访问。反过来如果保证 m n那么 j total_left - i 在 i 取 [0, m] 时一定落在 [0, n] 内。所以第一步永远先交换让短的数组做二分搜索的目标。3.3 如何判断 i 偏大还是偏小现在问题变成在 [0, m] 内二分查找合适的 i。每次取 mid 作为 i算出 j检查两个交叉条件。麻烦在于两个条件可能一个成立一个不成立如何决定往左还是往右搜方向判断的核心只有两条如果 nums1[i-1] nums2[j]说明左半里 nums1 的元素多了i 应当减小如果 nums2[j-1] nums1[i]说明左半里 nums2 的元素多了i 应当增大。注意讨论 nums1[i-1] 和 nums2[j-1] 时天然要求 i 0 和 j 0同时 nums1[i] 和 nums2[j] 也要求 i m 和 j n。这些边界之后统一用正负无穷处理先把方向搞清楚。直觉上可以这样理解你在两根长度不等的绳子上同时找切口要求切口左边总长固定。先猜一个位置如果发现左边某一段里有元素比右边还大说明这一侧切多了就往回收一点反之说明切少了就往外放一点。二分就是不断对“多了还是少了”做调整最终收敛到唯一正确位置。3.4 手工推演两个用例奇数和偶数路径先用奇数用例。nums1 [2]nums2 [1, 3]。此时 m1, n2已经是 m ntotal3total_left2。二分范围 [0, 1]取 i0j2。四个极值是a_left_max -INFa_right_min 2b_left_max 3b_right_min INF。检查a_left_max b_right_min不可能b_left_max a_right_min3 2成立说明 i 太小左边界变为 1。再取 i1j1。a_left_max2a_right_minINFb_left_max1b_right_min3。两个交叉条件都成立找到答案。total 为奇数直接返回 max(2, 1) 2。再用偶数用例。nums1 [1, 2]nums2 [3, 4]。m2, n2total4total_left2。取 i1j1。a_left_max1a_right_min2b_left_max3b_right_min4。第二个条件 b_left_max a_right_min3 2成立说明 i 太小左边界变为 2。取 i2j0。a_left_max2a_right_minINFb_left_max-INFb_right_min3。条件都不成立命中。total 为偶数返回 (max(2, -INF) min(INF, 3)) / 2 2.5。这两个用例覆盖了奇偶两条路径也顺带验证了交换数组后的处理逻辑。你会发现整个二分过程每次只根据一个比较结果移动边界和普通二分查找没有任何区别关键是搞清楚往哪个方向移动。4. 完整代码与边界条件index越界和奇偶陷阱复盘4.1 可直接运行的 Python3 主版本把上面的推导落成代码完整版本如下class Solution: def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float: m, n len(nums1), len(nums2) if m n: nums1, nums2 nums2, nums1 m, n n, m total_left (m n 1) // 2 left, right 0, m INF float(inf) while left right: i (left right) // 2 j total_left - i a_left_max -INF if i 0 else nums1[i - 1] a_right_min INF if i m else nums1[i] b_left_max -INF if j 0 else nums2[j - 1] b_right_min INF if j n else nums2[j] if a_left_max b_right_min: right i - 1 elif b_left_max a_right_min: left i 1 else: if (m n) % 2 1: return max(a_left_max, b_left_max) return (max(a_left_max, b_left_max) min(a_right_min, b_right_min)) / 2 return 0.0代码很短但每一行都有讲究。交换数组是为了保证 m n避免二分过程中 j 越界total_left 是左半元素数量四个 INF 赋值把边界情况变成普通情况。while 循环用 left right 的模板命中后直接返回不会出现死循环。4.2 四个 INF 边界值的作用i 0 时nums1 左侧一个元素都没有a_left_max 理应是“没有”但为了统一计算 max把它设成 -INF任何正常值都比它大它永远不会成为左半最大值。i m 时nums1 右侧没有元素a_right_min 设成 INF任何正常值都比它小它永远不会成为右半最小值。nums2 的边界同理。不这样处理的话你得写四五层判断去讨论 i 或 j 到达边界时哪些元素不存在。用 INF 之后边界元素自动被“架空”四个比较和最后的 max/min 计算全部照常进行。这是我在代码里最想强调的小技巧它比每个分支写 if 判断要清晰得多也不容易漏。提示手推这道题时建议把 -INF 和 INF 直接写成负无穷和正无穷别用具体大数比如 -10**9因为测试数据里可能出现更大的负数。4.3 我踩过的三个坑每一条都是真实报错第一个坑是忘记交换数组。我第一次写的时候直接在长数组上二分拿 nums1[1,3,5]、nums2[2] 测试m3, n1total_left2。二分取 i0 时 j2但 nums2 长度只有 1访问 nums2[j] 直接 IndexError。交换成短数组后j 的取值范围被约束在 [0,n] 内这类越界在结构上就不存在了。第二个坑是 total_left 写成了 (m n) // 2。偶数长度时没问题奇数长度时左半少了一个元素中位数直接错。比如 [1,3] 和 [2]正确中位数是 2写成 (mn)//2 后会得到 1.5。核心记忆点是total_left 永远用加一再整除保证奇数时左半多一个。第三个坑是二分循环条件用 left right结果在部分用例上死循环或找不到答案。因为 i 的搜索空间是闭区间 [0, m]命中条件需要比较到 left right 时的那一格用 left right 会漏掉。我后来统一用 left right命中后立即返回这个坑就再没踩过。注意记忆 total_left 时可以把它理解为“左侧比右侧多一个奇数时或相等偶数时”加一再整除是唯一正确写法。4.4 空数组和单元素数组验证空数组和单元素数组是最容易写崩的边界。比如 nums1 [], nums2 [1]。交换后依然 m0, n1total_left 1。循环只可能取 i0j1。此时 a_left_max -INFa_right_min INF因为 i m 成立b_left_max 1b_right_min INF。a_left_max b_right_min不成立b_left_max a_right_min不成立。直接命中奇数返回 max(-INF, 1) 1。再比如两个数组都有元素但其中一个较短nums1 [1], nums2 [2, 3, 4, 5]。m1, n4total5total_left3。二分 i 只有 0 或 1 两种可能无论哪种j 都不会越界。这类用例我建议你在本地多跑几组把奇偶、空数组、等长数组、差一个长度的数组全都覆盖一遍边界条件才能真正算过关。5. 复杂度对比与面试追问把这道题当作系统设计题来准备5.1 三种解法的复杂度对照给出一张表解法时间复杂度空间复杂度说明合并后排序O((mn) log(mn))O(mn)最简单但不利用有序性双指针归并O(mn)O(1)利用有序性仍在线性级别第 k 小淘汰O(log(mn))O(1)满足题目要求思路直观划分数组二分O(log(min(m,n)))O(1)最优解二分在短数组上面试时先把这张表在脑子里过一遍然后根据面试官要求决定讲多深。如果时间只剩十分钟直接写第 k 小版本是务实选择代码更快不容易出错如果面试官明显在考察你对二分的理解那划分数组法才是完整答案。5.2 换到 Java 或 C 时要注意的差异Python 里 (mn1)//2 没有类型风险但 Java 和 C 里要小心运算符和类型转换。我在写 Java 版本时习惯这样处理边界值int i (left right) 1; int j totalLeft - i; int aLeftMax (i 0) ? Integer.MIN_VALUE : nums1[i - 1]; int aRightMin (i m) ? Integer.MAX_VALUE : nums1[i];用 Integer.MIN_VALUE 和 Integer.MAX_VALUE 代替正负无穷返回结果时再转 double。注意 total_left 用 (m n 1) 1 时要加括号右移运算符优先级低于加法漏掉括号会算出完全错误的结果。C 里返回偶数中位数时 (max min) / 2.0 要带小数点写成 / 2 就是整数除法直接截断。5.3 面试官可能的追问与回答思路我总结了三个大概率被追问的点。第一“为什么只用两个交叉条件就能保证整个左半都小于右半”回答要点两个数组各自有序左半内部已有序右半内部已有序只需检查跨数组的相邻边界即 nums1 左侧最大值与 nums2 右侧最小值、nums2 左侧最大值与 nums1 右侧最小值。第二“如果数组里有重复元素条件还能用吗”回答能。条件里用的是 或 重复元素不会破坏划分有效性。比如 nums1[1,1,1], nums2[1,1]按公式枚举 i 依然能找到满足交叉条件的切点最终返回 1。第三“如果扩展到 k 个有序数组找中位数怎么做”回答可以用大小为 k 的堆维护每个数组当前指针指向的最小值逐次弹出到中位位置复杂度是 O(总元素数 * log k)也可以两两合并面试中通常只需要讲思路。这道题单拎出来的意义是让你掌握“两个数组上同时二分”的思想扩展到多数组时主要套递归和分治套路。我在面试中吃过一次亏当时只说了第 k 小解法面试官追问“能不能在短数组上二分”时我卡住了。后来我把这道题当成一次系统设计题来准备——先明确约束再画切分模型再推边界最后落到代码——这套流程对其他二分题目同样适用。最后分享一个我自己的刷题体会。这道题我一共刷了三轮第一轮看题解似懂非懂第二轮自己手推了二十组用例第三轮才能做到十分钟内无 bug 写出最优解。中位数这类题不怕慢怕的是背代码。建议你在看代码前先在草稿纸上画出两个数组和切点每次二分都标注 i、j、四个极值推完三个用例后再写代码那才是真正掌握了。
