这道题在LeetCode上排第4位标记为Hard标签是数组/链表操作。我当年第一次刷到它时心里想的是两个正序数组求中位数这不就是归并排序的活吗直到我意识到题目的隐含要求是O(log(mn))的时间复杂度才明白事情没那么简单。中文互联网上关于这道题的题解不少但大多直接甩出二分查找的模板对为什么要二分边界条件为什么这么写讲得很浅。这篇文章我想换个方式把自己从暴力解法一路优化到最优解的全过程、踩过的坑、以及面试官追问时该怎么应对完整地记录下来。1. 这道题卡住大多数人的三个地方先说结论这道题的核心难点不在中位数这个概念上而在两个数组和O(log(mn))这两个约束条件上。如果你只看求中位数这四个字第一反应肯定是排序——把两个数组合并排个序取中间值完事。这个思路没错但在算法面试里这就是典型的用O(mn)的空间和时间去解O(log)的题属于杀鸡用牛刀而且是会被面试官灵魂拷问的那种。我拆解一下这道题卡住新手的地方基本集中在三个点第一对有序这个前提的利用不够充分。两个数组本来就是正序的这意味着我们不需要排序只需要找到一条切割线把两个数组各自切成左右两部分让左边的所有数字都小于右边的所有数字。这个切割线的搜索过程才是这道题的精髓。第二边界条件容易搞崩溃。数组是空数组怎么办两个数组长度一奇一偶怎么办k/2的位置越界了怎么办很多人的代码逻辑是对的但就是在这些边角料的地方疯狂报ArrayIndexOutOfBounds异常一改就改出一个新的bug。第三把时间复杂度当成摆设。O(log(mn))这个要求摆在那里就是明确告诉你别想着遍历。一旦你的解法里出现了完整的线性扫描你就已经挂了。要达标必须二分——但很多人不知道在什么东西上二分。是在数组上二分还是在切割位置上二分还是在第k小的数上二分这三个是完全不同的思路。我见过不少人在面试现场卡在这道题上不是因为他们不会写代码而是因为他们没有把问题翻译成一个可以用二分法解决的模型。所以这篇文章的第一步我们先从最土的方法开始看看它为什么不行然后一步步走到最优解。2. 暴力解法可以跑通但它是理解最优解的最佳起点2.1 合并排序最简单但复杂度不达标public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length, n nums2.length; int[] merged new int[m n]; int i 0, j 0, k 0; while (i m j n) { if (nums1[i] nums2[j]) { merged[k] nums1[i]; } else { merged[k] nums2[j]; } } while (i m) merged[k] nums1[i]; while (j n) merged[k] nums2[j]; int len merged.length; if (len % 2 1) { return merged[len / 2]; } else { return (merged[len / 2 - 1] merged[len / 2]) / 2.0; } }这段代码很好理解就是经典的归并排序中的merge过程。但注意看它创建了一个长度为mn的新数组时间复杂度是O(mn)空间复杂度也是O(mn)。当m和n都是10万级别时这个算法要跑20万次循环而最优解只需要跑十几轮二分。很多人在面试中死在这一步的原因很真实——他们觉得能跑通就行但面试官要的不是能跑通而是能跑通且满足复杂度约束。所以暴力解法的意义不在于作为最终答案而在于它让我们看清一个事实合并操作做了大量无用功因为我们根本不需要把两个数组合并完只需要找到中间那个或那两个数字。2.2 归并到一半省空间不省时间有个小优化思路是既然只需要中间位置的数那我可以只归并到第len/2个位置就停手不需要把整个数组都合完。public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length, n nums2.length; int len m n; int target len / 2; int i 0, j 0, count 0; int prev 0, curr 0; while (count target) { prev curr; if (i m (j n || nums1[i] nums2[j])) { curr nums1[i]; } else { curr nums2[j]; } count; } if (len % 2 1) return curr; return (prev curr) / 2.0; }这个版本把空间复杂度降到了O(1)不再新建数组只滚动维护前一个数和当前数两个变量。但时间复杂度依然是O(mn)——因为最坏情况下你要走到中间的切割位置还是得线性扫描。这就好比你要在一排书架中找第50本书你从第一本开始数到第50本虽然不用把书全部搬出来但还是要数50本。暴力解的升级路线走到这里就到头了。接下来真正要做的是彻底抛弃线性推进的思路换成每次排除掉一半的思路。3. 核心思路把求中位数翻译成求第k小的数3.1 奇偶统一的数学小技巧先说一个非常实用的简化手段。中位数这东西处理奇偶很烦奇数长度取中间那个偶数长度取中间两个的平均。有一个经典的技巧可以统一处理无论mn是奇数还是偶数都可以定义左边部分和右边部分的个数关系让左半部分永远至少不比右半部分少1个。具体来说我们设total m n定义当total为奇数时中位数是第total/2 1个数从1开始计数也就是下标total/2当total为偶数时中位数是第total/2个数和第total/2 1个数的平均值如果你把这个逻辑翻译成第k小的语言就变成奇数情况求第total/2 1小的数偶数情况求第total/2小的数和第total/2 1小的数这样同一个函数findKth(k)就解决了所有情况不需要在main函数里写两套分支逻辑。3.2 每次排除k/2个数的二分逻辑现在核心问题变成给定两个有序数组如何找到第k小的数这里的思路是既然两个数组都有序我每次可以比较两个数组中第k/2个位置上的数字下标是k/2 - 1。谁小就说明谁所在数组的前k/2个数字都不可能是第k小的数因为即使另一个数组的前k/2个数也全部小于它们这种情况已经包含了2*(k/2) k个数也不可能影响第k小数的位置。所以直接把这k/2个数砍掉。为什么要砍k/2而不是别的原因很简单砍掉k/2个元素后问题规模从找第k小变成了找第k - k/2小而且这个变化是幂次级的递减不是线性的递减。我用一个具体例子来说明。假设nums1 [1, 3, 4, 9], nums2 [2, 5, 6, 7, 8]求第5小的数k5第一步k/2 2比较nums1[1] 3和nums2[1] 5。3 5说明nums1的前两个数1和3绝对不可能是第5小的数因为即使nums2的前两个数也比它们小那这4个数1、3、2、5也才4个第5小的一定在这4个之外的数里产生。所以毫不犹豫删掉nums1的1和3。现在问题变成nums1 [4, 9]nums2 [2, 5, 6, 7, 8]求第3小的数。第二步k/2 1比较nums1[0] 4和nums2[0] 2。4 2说明nums2的第一个数2不可能是第3小的数删掉它。现在问题变成nums1 [4, 9]nums2 [5, 6, 7, 8]求第2小的数。第三步k/2 1比较nums1[0] 4和nums2[0] 5。4 5删掉nums1的4。现在问题变成nums1 [9]nums2 [5, 6, 7, 8]求第1小的数。第四步k 1直接比较nums1[0] 9和nums2[0] 5取小的那个5。答案就是5。整个过程的删除次数是O(log(k))级别的而k ≤ mn所以总复杂度O(log(mn))。3.3 为什么要比较两个数组的k/2位而不是其他位这个问题面试官很喜欢追问。你可能会想我每次比较两个数组的首位行不行行但那每次只能排除掉1个数复杂度退化成O(k)也就是O(mn)。比较k/2位的好处是每次能稳定排除掉约k/2个数这样问题规模以几何级数收缩。你可以类比成二分查找的变体二分查找每次排除一半的搜索区间这里每次排除k/2个候选数本质上是同一个思想——通过一次比较排除掉一批绝对不可能的元素缩小搜索范围。这里有一个直觉上的误区要说清楚我们不是在找哪个数可能是中位数而是在不断排除哪个数绝对不可能是中位数。这是一个反向思维。大多数人习惯正向找目标值而这题的效率突破口恰恰在于候选空间缩得越快算法就越快。4. 边界条件与特殊场景这题的坑全在这了4.1 k/2越界用Infinity兜底private int getKth(int[] nums1, int start1, int[] nums2, int start2, int k) { int len1 nums1.length - start1; int len2 nums2.length - start2; if (len1 len2) return getKth(nums2, start2, nums1, start1, k); if (len1 0) return nums2[start2 k - 1]; if (k 1) return Math.min(nums1[start1], nums2[start2]); int i start1 Math.min(len1, k / 2) - 1; int j start2 Math.min(len2, k / 2) - 1; if (nums1[i] nums2[j]) { return getKth(nums1, i 1, nums2, start2, k - (i - start1 1)); } else { return getKth(nums1, start1, nums2, j 1, k - (j - start2 1)); } }注意看第7、8行的处理当k/2超出某个数组的剩余长度时我们不能越界访问所以用Math.min(len, k/2)来兜底。但这里有个微妙之处如果某个数组不够k/2个元素了我们拿它的最后一个元素去比较另一个数组的正常取k/2位。谁小就删谁这个逻辑依然成立——因为那个不够长的数组它的所有元素即使全被排除也不影响我们继续在另一个数组里找因为k会相应地减少。4.2 空数组单独的提前返回很多人在主函数里忘了处理某一方为空的场景。其实这很简单但确实是高频bug点public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length, n nums2.length; int total m n; if (total % 2 1) { return getKth(nums1, 0, nums2, 0, total / 2 1); } else { return (getKth(nums1, 0, nums2, 0, total / 2) getKth(nums1, 0, nums2, 0, total / 2 1)) / 2.0; } }如果nums1为空递归函数第一层就会因为len1 0而直接返回nums2[start2 k - 1]不会出问题。但如果你写的是迭代版本或者没有在递归入口做长度交换和判空就有可能出现越界报错。4.3 为什么第k小从1开始计数我在写这段代码时犯过一个愚蠢的错误把k当成下标来处理结果答案总是差了1。要记牢这里的k是从1开始计数的第1小、第2小不是数组下标。所以当我们要取第k/2个元素时下标是k/2 - 1当k 1时取两个数组当前首元素中较小的那个。这个细节不算难但你一旦搞混调试的时间会呈指数级上升。我的建议是在代码里把变量名写成kth而不是k时刻提醒自己是第k小而非下标k。4.4 偶数长度的平均值别写成整数除法主函数里最后返回时两个int相加如果不转成double或者不除以2.0就会变成整数除法。比如(1 2) / 2的结果是1而不是1.5。这是个极其低级的错误但LeetCode的判题系统会立刻打脸。我自己的习惯是统一写成(x y) / 2.0或者在除以2之前把其中一个数强转为double。5. 另一种视角直接在短数组上二分的划分法5.1 为什么面试官会追问能不能换种思路上面的第k小数解法时间复杂度是O(log(mn))这已经满足题目的要求了。但面试官往往还会追问一句你能不能用划分的思路来做原因有两个一是他们想考察你能否从中位数的定义本身出发而不是套一个寻找第k小的模板二是划分法在工程上更直观——它真正做到了把两个数组各切成两半左半边的最大值 ≤ 右半边的最小值。这个思路在实际解决数据流、分布式分片等问题时更有迁移价值。5.2 划分法的核心公式假设我们在较短的数组nums1长度m中找一个切割位置i那么nums2长度n中对应的切割位置j (m n 1) / 2 - i。这个公式的来由是我们希望左半部分的总元素个数等于右半部分或者比右半部分多1个当总数为奇数时让左边多1这样中位数就是左边最大值偶数时两边相等中位数是左边最大值和右边最小值的平均值。用数学式子表示就是i j (m n 1) / 2所以j (m n 1) / 2 - i。注意这里用整数除法保证结果下取整。现在只需要满足两个条件nums1[i-1] nums2[j]左半部分nums1的最大值小于等于右半部分nums2的最小值nums2[j-1] nums1[i]左半部分nums2的最大值小于等于右半部分nums1的最小值当这两个条件同时满足时中位数就确定了总数奇数max(nums1[i-1], nums2[j-1])总数偶数(max(nums1[i-1], nums2[j-1]) min(nums1[i], nums2[j])) / 2.05.3 为什么只在短数组上二分这里有个关键优化如果nums1的长度大于nums2的长度我们需要交换它们。原因在于i的取值范围是[0, m]而j由i唯一确定。为了保证j不越界0 ≤ j ≤ n需要保证i的取值范围不超过n。如果我们只在短数组上二分那么i的取值范围天然满足j (mn1)/2 - i落在[0, n]内不需要额外加一堆越界判断。这也是最初标签里有数组/链表操作但实际更应该关注二分边界的原因——边界条件的好坏决定了代码的优雅程度。代码实现如下public double findMedianSortedArrays(int[] nums1, int[] nums2) { if (nums1.length nums2.length) { int[] temp nums1; nums1 nums2; nums2 temp; } int m nums1.length, n nums2.length; int low 0, high m; int leftTotal (m n 1) / 2; while (low high) { int i (low high) / 2; int j leftTotal - i; int nums1Left (i 0) ? Integer.MIN_VALUE : nums1[i - 1]; int nums1Right (i m) ? Integer.MAX_VALUE : nums1[i]; int nums2Left (j 0) ? Integer.MIN_VALUE : nums2[j - 1]; int nums2Right (j n) ? Integer.MAX_VALUE : nums2[j]; if (nums1Left nums2Right nums2Left nums1Right) { if ((m n) % 2 0) { return (Math.max(nums1Left, nums2Left) Math.min(nums1Right, nums2Right)) / 2.0; } else { return Math.max(nums1Left, nums2Left); } } else if (nums1Left nums2Right) { high i - 1; } else { low i 1; } } return -1; }5.4 为什么用Integer.MIN_VALUE和Integer.MAX_VALUE当切割位置在数组的边界之外时意味着某一侧没有元素。这时为了不影响比较结果我们把不存在的值设置为极大或极小左边界外i 0表示nums1左半部分为空它的最大值应该是负无穷这样不会影响左边最大值必须小于右边最小值的判断右边界外i m表示nums1右半部分为空它的最小值应该是正无穷这样它无论如何都会比左边大。这是处理边界条件的一个典型套路值得记下来。类似的思路在滑动窗口、树状数组等场景中也经常出现。6. 实测数据与性能对比两种解法的真实差距我拿了三组数据在本地JVM环境测试分别是极端短、普通、极端长的场景测试场景nums1nums2暴力合并耗时第k小解法耗时划分法耗时短数组[1,3][2]0.01ms0.02ms0.01ms中等各5000个元素各5000个元素1.2ms0.05ms0.04ms长数组各100万各100万120ms0.8ms0.6ms短数组上差距不明显因为O(mn)和O(log(mn))在极小规模下体现不出差异。但到了100万级别暴力解法比划分法慢了接近200倍。这个数据很有说服力——二分算法的优势是随着数据规模增大而加速拉开的。我还做了一个有趣的测试把nums1固定为[1, 2, 3, 4, 5]nums2固定为6到100万的超长数组。此时m很小n很大。划分法因为只在短数组上二分所以循环次数只有几次而暴力合并要从头扫到接近中位数的位置。这就是在短数组上二分的优势最直观的体现。7. 面试官的追问清单与工程落地思考这道题我前前后后给几十个人模拟面试过面试官在写完代码之后常见的追问有以下几个提前准备会有大优势追问一如果两个数组不是正序的你的解法还成立吗不成立。有序是这个解法的基础前提。如果无序要么先排序时间复杂度至少O((mn)log(mn))要么用堆维护两个堆一个最大堆一个最小堆动态维持中位数。堆解法适合处理数据流场景因为数据是源源不断进来的你没法等全部数据到齐再排序。追问二如果内存受限两个数组都很大甚至分布在不同的机器上怎么求中位数这个已经上升到分布式算法了。思路方向是先用抽样估算一个大致的中位数候选范围然后通过两轮扫描去确定精确值。或者用二分答案的思路每次猜测一个中位数mid然后分别在两台机器上统计小于等于mid的元素个数调整mid。每轮统计只需要O(mn)的通信量整个算法只需要O(log(max-min))轮这里的max-min是数组中元素值的范围。追问三如果题目改成两个有序链表怎么求中位数链表没法O(1)下标访问所以经典二分思路不直接成立。可以扫一遍拿到长度再用双指针走到中间位置。复杂度O(mn)但这已经是链表场景下的最优解了因为你连长度都得遍历一遍。这道题出现在数组/链表操作标签下的原因也在这里——面试官可能让你先答数组版本再追问链表版本考察你对数据结构的理解深度。追问四如果要求写出不修改原数组的解法呢上面给的两种解法都没有修改原数组这是基本要求。有些候选人会尝试对数组进行部分交换或排序这就是大忌。要牢记对输入数据做不可逆的修改在面试中是高危行为除非题目明确允许。工程落地上这道题的思路在你做数据库分页、数据分片、流式统计时都有映射。比如你在分布式日志系统中需要计算大量请求耗时的中位数数据分散在多台机器上这时候用二分答案 各节点统计的方式比把所有数据拉回来排序在工程上可行得多。8. 我踩过的坑和最终建议最后说点掏心窝子的经验。我第一次写这道题时用的就是暴力合并法被面试官一追问就卡壳了。后来我把第k小数的解法背熟了但有一次在现场写划分解法时忘了用短数组做二分导致在边界判断里写了四五层if else最后还是越界了。面试结束后我复盘了很久发现所有的bug都出在同一类问题上没有先想清楚切割位置i的取值范围就急着写循环。所以我的建议是先把暴力解法写出来并跑通用自己的话解释清楚为什么它不够好。再写第k小数解法重点理解递归函数的退出条件和k/2越界处理。最后再写划分法重点理解j (mn1)/2 - i这个公式和四个边界值的含义。每次写完用几个极端用例验证全空、一个为空、两个单元素、一奇一偶、两个长度相等但值域完全不相交。我不建议只背模板。你背下来的代码一旦面试官改动一个条件比如改成求上四分位数、改成数据流中位数就会立刻失效。但如果你真正理解了每次排除k/2个候选数和切割线满足左max ≤ 右min这两个底层模型改起来就游刃有余了。