刷题刷到 LeetCode 第 4 题“寻找两个正序数组的中位数”时很多人的第一反应是合并两个数组排个序取中间值不就行了但真正做进去才发现这题的难度标签“困难”一点都不虚难的不是“找中位数”而是那道硬性要求——时间复杂度必须达到 O(log(mn))。LeetCode 上它的标签是数组、二分查找、分治也是面试中高频出现的一道“区分度题”。这篇文章我会从双指针合并讲到二分切分把边界处理和踩坑经验一并写透适合刚刷 LeetCode 的选手建立思路也适合准备面试、想把这题一次性讲明白的同学深挖原理。1. 这道题到底在考什么1.1 题目长什么样为什么它是“困难”题目描述很简单给定两个正序数组 nums1 和 nums2长度分别为 m 和 n返回它们合并后的中位数要求时间复杂度 O(log(mn))。“正序”这两个字是关键它意味着两个数组内部都是从小到大排好序的不用再排序。这也是后面能用二分的大前提。很多人刚拿到这题第一反应是直接把两个数组合并成一个新数组然后排序取中位数。这个做法在功能上完全正确但问题在于时间复杂度是 O((mn)log(mn))比题目要求的 O(log(mn)) 差了一个数量级。面试时如果只给出这种解法基本等于告诉面试官“你没理解这道题的考点”。还有一种做法是双指针合并时间复杂度 O(mn)。这个比排序好一些但依然不满足题目要求。换句话说这题真正的门槛在于数组本身是有序的却被要求用对数级的解法这就逼着你去想“到底能不能不合并数组就找出中位数”。1.2 中位数的本质把数据切成两半教科书里对中位数的定义是把一列数从小到大排序如果总数是奇数取最中间那个如果总数是偶数取中间两个数的平均值。但站在算法设计的角度我更愿意把它理解为另一种等价说法“把数据一刀切两半左边数量和右边数量相差不超过 1并且左边最大值小于等于右边最小值”。这个理解是解这道题的核心。为什么因为中位数本质上描述的是一个“分割点”而不是某个具体的元素。一旦你接受了这个视角两个有序数组找中位数的问题就变成了在两个数组之间找一条虚拟的分割线让分割线左边元素的总数等于右边或比右边多一个同时保证左边所有元素都不大于右边所有元素。生活化一点的类比想象有两排按身高排好的队伍你想找出所有队员身高的中位数。暴力做法是让两排人合并成一排再数一遍聪明的做法是让两排人站在原地不动只在两队之间画一条虚拟的线调整这条线的位置直到线左边人数等于线右边并且线左边最高的人不比线右边最矮的人高。这条线在哪里中位数就在哪里。举个例子nums1 [1,3,5]nums2 [2,4,6]合并后是 [1,2,3,4,5,6]中位数是 (34)/2 3.5。合并后左边三个元素是 [1,2,3]左边最大值是 3右边三个元素是 [4,5,6]右边最小值是 4。分割线就要放在 3 和 4 之间。理解了这一点接下来不管是双指针还是二分都围绕“找这条分割线”展开。2. 先写能用的解法O(mn) 双指针合并2.1 双指针模拟合并的思路和代码不新建数组用两个下标 p1 和 p2 分别指向 nums1 和 nums2 的当前位置每次比较两个指针指向的元素把较小的那个取出来“视为”合并后的下一个元素然后移动对应指针。因为中位数只关心合并后中间位置的一个或两个元素所以我们只需要一路取到第 total 个元素就行不需要真的把整个合并数组存下来。实现时有个小技巧为了处理偶数长度的情况需要记录“上一个取出的元素”和“当前取出的元素”。当总长度是偶数时中位数就是这两个元素的平均值当总长度是奇数时中位数就是当前取出的元素。public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length, n nums2.length; int len m n; int left -1, right -1; int p1 0, p2 0; for (int i 0; i len / 2; i) { left right; if (p1 m (p2 n || nums1[p1] nums2[p2])) { right nums1[p1]; } else { right nums2[p2]; } } if ((len 1) 1) { return right; } return (left right) / 2.0; }这个解法里有个细节值得说一下判断p1 m (p2 n || nums1[p1] nums2[p2])的意思是只有当 nums1 没取完并且 nums2 取完了或者 nums1 当前元素更小时才从 nums1 取。否则从 nums2 取。这样就把“某个数组已经取空”的情况一并处理了不用单独写两个 if 分支。2.2 双指针解法为什么过不了面试官这关双指针合并的思路清晰、代码短、不容易写错作为热身完全可以但它的时间复杂度是 O(mn)并没有达到题目要求的 O(log(mn))。面试官让你做这道题要听的基本就是二分方案。你再想想如果两个数组长度都是 10 万O(mn) 意味着要扫描 20 万个元素而 O(log(min(m,n))) 只需要大约 17 次比较差距是非常明显的。另一个角度看双指针是“模拟合并”它没有利用“数组有序”这个条件去跳跃查找。中位数的位置本质上是一个“排名”概念你完全可以按照排名直接跳到目标位置附近而不是逐个元素数过去。这个跳跃查找的思路就是下一章要讲的二分切分。3. 最优解二分切分O(log(min(m,n)))3.1 先定“左侧元素总数”totalLeft (mn1)/2回到切分线的思路。假设我们在两个数组之间画一条切分线nums1 左侧分到 i 个元素nums2 左侧分到 j 个元素。那么左侧元素总数 ij 必须等于总长度的一半向上取整。写成公式就是totalLeft (m n 1) / 2这个式子里的 1 很关键。你可以自己推一下如果 mn 是偶数比如总长度 6那么 (61)/2 在整数除法下等于 3左侧恰好是 3 个元素如果 mn 是奇数比如总长度 5(51)/2 等于 3左侧有 3 个元素比右侧多 1 个。所以一个式子就能统一奇偶两种情况多余的那 1 个元素先放在左侧最后求值的时候再根据奇偶决定怎么处理。于是问题的维度瞬间从“两个变量的组合”降成了“一个变量”只要确定了 ij 就被自动确定了因为 j totalLeft - i。我们接下来要做的事情就是在 nums1 里找到那个合适的 i让分割线左右两边满足大小关系。3.2 切分条件四个边界值必须满足的大小关系分割线合法必须满足两个跨数组条件nums1 左侧最大值小于等于 nums2 右侧最小值也就是nums1[i-1] nums2[j]nums2 左侧最大值小于等于 nums1 右侧最小值也就是nums2[j-1] nums1[i]为什么要做跨数组比较而不是只比较各自数组内部的左右因为 nums1 内部天然升序nums1[i-1] nums1[i]恒成立不需要管nums2 同理。真正需要保证的是“左侧整体最大值 右侧整体最小值”。左侧最大值是max(nums1[i-1], nums2[j-1])右侧最小值是min(nums1[i], nums2[j])。只要上面两个条件同时成立就等价于这个整体关系成立。为了统一处理边界我们约定当 i0 时nums1[i-1] 不存在把它视为负无穷当 im 时nums1[i] 不存在视为正无穷。j 的边界处理同理。在代码里负无穷和正无穷可以用Integer.MIN_VALUE和Integer.MAX_VALUE充当哨兵。这样写的好处是四个边界值始终存在不用担心数组越界判断逻辑可以保持对称统一。3.3 用二分法在短数组上找 i现在的问题变成了i 取什么值才能让四个边界值满足上面两个条件最笨的办法是从 0 到 m 挨个试。但我们可以观察一个单调性当 i 增大时nums1[i-1] 和 nums1[i] 都会变大因为 nums1 升序而由于 j totalLeft - ij 会减小所以 nums2[j-1] 和 nums2[j] 都会变小。这意味着如果nums1[i-1] nums2[j]说明 nums1 左侧最大值太大了nums1 分给左侧的元素太多需要把 i 调小。如果nums2[j-1] nums1[i]说明 nums2 左侧最大值太大了nums1 分给左侧的元素还不够需要把 i 调大。两个判断条件都随 i 单调变化于是可以放心地在 [0, m] 区间上做二分查找每轮把搜索范围缩小一半。这里还有一个重要优化应该始终让较短的数组作为 nums1。原因有两点。第一二分次数取决于 i 的搜索范围范围越大二分次数越多选短数组能让复杂度变成 O(log(min(m,n)))。第二更关键的是当 m n 时j totalLeft - i 天然落在 [0, n] 范围内不会出现越界如果让长数组作为被二分的对象j 就容易滑出边界带来额外的处理麻烦。到这里整个二分的框架已经立住了。下一步就是把它写成能跑的代码并且把边界条件逐一拆开看。4. 完整代码与边界细节4.1 代码实现Java下面这个版本用的是 while (left right) 完整双条件判断思路最直观也最容易在面试时讲清楚public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 保证 nums1 是较短数组 if (nums1.length nums2.length) { int[] tmp nums1; nums1 nums2; nums2 tmp; } int m nums1.length; int n nums2.length; int totalLeft (m n 1) / 2; int left 0; int right m; while (left right) { int i (left right) / 2; // nums1 分给左侧的元素个数 int j totalLeft - i; // nums2 分给左侧的元素个数 // 用哨兵统一处理 i0 / im / j0 / jn 的边界 int aLeft (i 0) ? Integer.MIN_VALUE : nums1[i - 1]; int aRight (i m) ? Integer.MAX_VALUE : nums1[i]; int bLeft (j 0) ? Integer.MIN_VALUE : nums2[j - 1]; int bRight (j n) ? Integer.MAX_VALUE : nums2[j]; if (aLeft bRight) { // nums1 左侧最大值太大nums1 分多了i 要左移 right i - 1; } else if (bLeft aRight) { // nums2 左侧最大值太大nums1 分少了i 要右移 left i 1; } else { // 找到合法切分 if (((m n) 1) 1) { return Math.max(aLeft, bLeft); } return (Math.max(aLeft, bLeft) Math.min(aRight, bRight)) / 2.0; } } return 0.0; // 理论上不会走到这里 }这段代码有几个值得注意的细节。第一个细节是交换数组。开始先判断nums1.length nums2.length如果成立就交换保证后续二分的对象始终是短数组。这个交换不会影响中位数的值因为两个数组的角色互换了但内容不变。第二个细节是totalLeft (m n 1) / 2。在 Java 中int 除法自动向下取整。我们前面推过这个式子同时兼容奇偶两种情况。第三个细节是哨兵赋值。aLeft表示 nums1 左侧最大值bLeft表示 nums2 左侧最大值aRight表示 nums1 右侧最小值bRight表示 nums2 右侧最小值。当某个数组在分割线一侧没有元素时用极值代替保证比较逻辑不走特殊分支。第四个细节是最后的结果计算。奇数长度时左侧比右侧多一个元素中位数就是左侧最大值max(aLeft, bLeft)偶数长度时中位数是左侧最大值和右侧最小值的平均值。除法记得用/ 2.0而不是/ 2否则整数除法会把小数部分丢掉。4.2 边界条件逐一拆解空数组的情况。假设 nums1 为空m0。此时 i 只能取 0j totalLeft。aLeft 是负无穷aRight 是正无穷bLeft 和 bRight 分别是 nums2 中分割线两侧的元素。判断条件会直接收敛到正确位置结果退化为在 nums2 里找中位数。代码不需要为空数组单独写分支。i0 或 im 的情况。i0 表示 nums1 整个数组都被分到分割线右侧nums1 左侧一个元素都没有im 表示 nums1 整个数组都在左侧。这两种情况分别由负无穷和正无穷哨兵兜住不会越界。j0 或 jn 同理。奇数长度和偶数长度的差异。核心区别在最后一步奇数长度时直接取左侧最大值偶数长度时取左侧最大值与右侧最小值的平均。前面算 totalLeft 时统一了左侧元素个数最后一步再区分奇偶逻辑是清晰的。潜在的大数溢出。题目本身的数组长度一般不会太大但如果你在写变体题mn 可能接近 int 上限。稳妥的做法是用(m n 1) 1或者先把 m、n 转成 long 计算再转回 int。4.3 Python 版本与运行时注意Python 写法和 Java 几乎一样主要区别在于用float(-inf)和float(inf)表示负无穷和正无穷以及除法直接用/就能得到浮点结果def findMedianSortedArrays(nums1: list[int], nums2: list[int]) - float: if len(nums1) len(nums2): nums1, nums2 nums2, nums1 m, n len(nums1), len(nums2) total_left (m n 1) // 2 left, right 0, m while left right: i (left right) // 2 j total_left - i a_left float(-inf) if i 0 else nums1[i - 1] a_right float(inf) if i m else nums1[i] b_left float(-inf) if j 0 else nums2[j - 1] b_right float(inf) if j n else nums2[j] if a_left b_right: right i - 1 elif b_left a_right: left i 1 else: if (m n) % 2 1: return max(a_left, b_left) return (max(a_left, b_left) min(a_right, b_right)) / 2.0 return 0.0这里唯一容易踩坑的是 Python 的整数除法//它也是向下取整和 Java 的/行为一致所以 total_left 的写法没问题。如果你用的是 Python 2/在整数之间是整除但现在已经很少见不展开说了。5. 常见问题、踩坑记录与调试技巧5.1 常见问题速查表我把这道题里大家最容易踩的坑整理成了表格方便对照排查。常见问题可能原因解决办法死循环程序跑不完二分更新时写成left mid而不是left mid 1导致区间无法收缩严格按照条件分别用right i - 1和left i 1更新数组越界访问没有处理 i0、im、j0、jn 四种边界用负无穷/正无穷哨兵统一处理或在比较前加边界判断结果为整数而不是小数偶数长度时用了/ 2整数除法丢失小数写成/ 2.0或用 Python 的浮点除法结果差一个数totalLeft 忘记加 1导致奇偶长度时左侧元素个数不对记住公式totalLeft (m n 1) / 2二分收敛到错误位置没有先交换数组让长数组作为二分对象导致 j 越界后判断错乱先处理if (nums1.length nums2.length) swap面试讲不清原理只背代码不理解 j totalLeft - i 的推导拿具体例子手推一遍见 5.25.2 现场调试记录用测试用例验证算法拿一个小例子手推一遍比看十遍代码更有用。我们用 nums1 [1,3]nums2 [2,4,5] 来验证。m2n3totalLeft (231)/2 3。初始 left0right2。第一次循环i(02)/21j3-12。四个边界值分别是 aLeft1aRight3bLeft4bRight5。检查条件aLeft(1) bRight(5) 不成立bLeft(4) aRight(3) 成立说明 nums1 分给左侧的元素太少需要右移left i1 2。第二次循环left2right2i2j3-21。aLeft3aRight正无穷因为 imbLeft2bRight4。检查条件aLeft(3) bRight(4) 不成立bLeft(2) aRight(正无穷) 不成立找到合法切分。总长度 5 是奇数中位数 max(3,2) 3。合并数组 [1,2,3,4,5] 的中位数确实是 3验证通过。偶数例子再看一眼nums1[1,2]nums2[3,4]。m2n2totalLeft(221)/22。第一次循环i1j1aLeft1aRight2bLeft3bRight4。bLeft(3) aRight(2)说明 i 太小left2。第二次循环i2j0aLeft2aRight正无穷bLeft负无穷bRight3。两个条件都不成立命中。总长度偶数中位数 (max(2,负无穷) min(正无穷,3)) / 2 (23)/2 2.5与预期一致。手推的时候建议把 i、j、aLeft、aRight、bLeft、bRight 六个值逐轮列出来就像上面这样。这个过程能帮你建立对二分切分的直觉面试时即使忘了代码也能从推导中现场写出来。5.3 刷完这道题后还可以延伸思考什么这道题的二分切分思想可以推广到“寻找两个有序数组的第 k 小数”。做法是每次比较 nums1[k/2-1] 和 nums2[k/2-1]把较小一侧的前 k/2 个元素排除掉k 随之缩小一半直到 k 变为 1。本题其实就是第 k 小数的一个特例当总长度 mn 时中位数就是第 (mn1)/2 个数奇数情况或第 (mn)/2 和第 (mn)/21 两个数的平均值偶数情况。所以完全可以用一个递归的 kth 函数来解本题逻辑更抽象但更加通用。对二分和滑动窗口感兴趣的还可以继续做“滑动窗口中位数”和“数据流中的中位数”这两道题。前者要结合堆或双优先队列后者考验动态场景下维护中位数的能力。做过第 4 题之后再碰这些题目你对中位数本质的理解会扎实很多。我个人把这道题刷了三遍才真正弄懂“切分线”的含义。第一遍只会双指针合并代码过了但面试官追问二分时答不上来第二遍背下了二分代码能默写但讲不出 j 为什么等于 totalLeft - i第三遍静下心拿各种小用例手推才彻底理解四个边界值的关系。最后分享一个经验二分题特别适合用具体例子手推每次推完记录 i 和 j 的变化坚持几道题之后你会发现再遇到二分查找的难题思路会清晰很多。