我一开始接触这道题的时候觉得它就是个简单的“归并排序取中间值”问题不就是把两个数组合并起来然后按下标取值吗直到我读到题目里那个O(log(mn))的时间复杂度要求才意识到事情没那么简单。这道题是数组二分操作里非常经典的一道也是常被拿来考“你是不是真懂二分搜索”的试金石。无论你是在准备算法面试还是日常写业务代码时遇到“两份有序数据求整体分位点”的需求这套思路都用得上。所谓“寻找两个正序数组的中位数”说白了就是给定两个从小到大排好的数组把两者看成一个整体后找出这个整体序列中间位置的数值。看起来朴素但难点全在那句“对数级时间复杂度”上。这篇我会把两种主流解法都拆开讲透一种是“第 K 小元素”的排除法一种是“划分数组”切割法并附上完整的实现代码、边界处理说明和一份避坑清单。1. 题目拆解标题里藏着的三个关键词1.1 “正序数组”意味着什么先聊“正序”。这俩字是整个题目的信息红利所在。如果一个数组是无序的你找中位数最快也得先排序O(n log n)起步。但只要数组有序你就可以用二分查找、双指针这类“利用位置信息”的手段把搜索范围成半点地缩小。这也是我在实际工作中非常依赖的直觉有序数据是无价的。无论是数据库索引、日志时间序列还是接口返回的已排序列表遇到这类数据第一步不是遍历而是先想想“能不能二分”。本题目里的两个正序数组就是给你两块积木让你通过位置比较来快速收敛答案。1.2 “中位数”的本质是第 K 小的数很多同学一上来就纠结奇偶性其实完全没必要。中位数的定义可以统一成一句话在长度为total的有序序列里中位数是第total/2 1个元素奇数情况或者第total/2和第total/2 1个元素的平均值偶数情况。所以这道题本质上可以转化为一个更通用的子问题两个正序数组中如何找第 K 小的数。一旦你写出了getKth函数中位数不过就是调用它两次取平均而已。总长度 total m n 若 total 为奇数中位数 第 (total/2 1) 小的数 若 total 为偶数中位数 (第 total/2 小的数 第 (total/2 1) 小的数) / 2举个例子nums1 [1, 3]nums2 [2]total 3。我们需要第3/2 1 2小的数合并后是[1, 2, 3]第2小是2中位数就是2。而nums1 [1, 2]nums2 [3, 4]total 4需要第2小和第3小的平均数也就是2和3的平均值2.5。1.3 为什么复杂度要求是 O(log(mn))如果允许O(mn)代码五分钟就能写完双指针归并走到中间两格取平均。但题目要求的O(log(mn))直接把这条路堵死了。这个复杂度恰恰暴露了出题人的真实意图它不满足于“你会写循环”它想考的是“你懂不懂排除一半”。log(mn)级别的算法每轮操作必须能丢掉大约一半的候选元素。这就逼着你想能不能像二分查找那样每次比较两个数组中的某个位置然后一次性排除掉不可能包含答案的那一片区域答案是肯定的。这也是整道题最核心的思维跳跃点。2. 解法一二分排除法每次丢掉一半2.1 先把问题转化成“找第 K 小的数”二分排除法也叫“第K小排除法”的思路非常直白既然要在两个有序数组中找第K小的数那我每次就设法排除掉K/2个候选元素让K不断减小。当 K 缩小到 1 时问题就变得极其简单两个数组剩余部分的最小值就是答案。我可以用一个例子把流程走一遍。假设nums1 [1, 3, 5, 7, 9] nums2 [2, 4, 6, 8, 10] K 5第一轮K/2 2。比较nums1的第2个元素3和nums2的第2个元素4。因为3 4那么nums1的前2个元素1, 3绝对不可能是全局第5小的元素——原因是比它们小的元素最多只有nums1里的1个和nums2里的1个合计最多3个。所以这2个元素可以直接丢掉。K 变成5 - 2 3。第二轮两个数组的剩余部分分别是nums1 [5, 7, 9]和nums2 [2, 4, 6, 8, 10]。K/2 1。比较第1个元素5和2。2 5丢掉nums2的第1个元素2。K 变成2。第三轮剩余部分是nums1 [5, 7, 9]nums2 [4, 6, 8, 10]。K/2 1。比较5和44 5丢掉4。K 变成1。此时K等于1直接返回两个数组剩余的最小值即min(5, 6) 5。我们验证一下两个数组合并后是[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]第5小的数确实是5。2.2 为什么比较 K/2 位置是合理的你可能会问为什么选K/2而不是选K/3或者别的核心原因是想要在 O(logK) 内完成每轮都要把 K 减少固定的比例而选 K/2 是最自然、最好写的比例。细想一层如果nums1[K/2 - 1] nums2[K/2 - 1]说明nums1的前 K/2 个元素中任意一个元素x在另一个数组里能找到多少个比x小的元素最坏情况下nums2的前 K/2 - 1 个元素也可能全部小于x加上nums1自身排在x前面的那些元素比x小的元素总数最多也就是(K/2 - 1) (K/2 - 1) K - 2个仍然小于 K-1。换句话说这 K/2 个元素里不可能有全局第K小排除它们没有任何风险。这个“排除一定不可能是答案的元素”的手法和二分查找里“砍掉不可能区间”的本质一模一样。2.3 完整实现与边界设计下面给出我常用的Java版本用了两个索引i和j分别指向两个数组的剩余起点没有实际拷贝数组空间开销只是 O(1)。public double findMedianSortedArrays(int[] nums1, int[] nums2) { int total nums1.length nums2.length; if (total % 2 1) { return getKth(nums1, nums2, total / 2 1); } else { return (getKth(nums1, nums2, total / 2) getKth(nums1, nums2, total / 2 1)) / 2.0; } } private int getKth(int[] nums1, int[] nums2, int k) { int m nums1.length, n nums2.length; int i 0, j 0; while (true) { if (i m) { return nums2[j k - 1]; } if (j n) { return nums1[i k - 1]; } if (k 1) { return Math.min(nums1[i], nums2[j]); } int half k / 2; int newI Math.min(i half, m) - 1; int newJ Math.min(j half, n) - 1; if (nums1[newI] nums2[newJ]) { k - (newI - i 1); i newI 1; } else { k - (newJ - j 1); j newJ 1; } } }我重点说说几处边界newI和newJ为什么要用Math.min(i half, m) - 1因为k/2可能比数组剩余长度还大。比如nums1只剩 1 个元素但k 5那i half就会越界。取min的意思是我最多只能排除这个数组剩余的全部元素不能超出数组边界。排除元素数量用newI - i 1而不是直接用half。因为上面做了截断实际排除的可能比half少。比如一个数组本身只剩 3 个元素half 4你只能排除 3 个。当k 1时直接返回两个数组当前头部较小的那个。这也是递归/循环的终止条件。2.4 时间复杂度的直观证明每轮循环K 至少减半。K 的初始值是(mn)/2级别最坏情况下经过 O(log(mn)) 轮K 会降到 1。每轮只有常数次比较所以整体时间复杂度是 O(log(mn))空间复杂度 O(1)。我实际测试过这个方法在极端情况下的表现比如nums1为空、nums2长度为百万级别它也能在几十次比较内出结果远快于归并。3. 解法二划分数组法从切割的视角理解3.1 核心思想在两个数组里各自切一刀二分排除法的逻辑很“动态”每轮都在排除。另一种更符合“中位数定义”的思路是把两个数组分别切成左右两段使得左半部分的元素总数刚好等于右半部分或比右半部分多一个而且左半部分的最大值不大于右半部分的最小值。假设在nums1的第i个元素后面切一刀在nums2的第j个元素后面切一刀那么nums1 左半部分nums1[0 .. i-1] nums1 右半部分nums1[i .. m-1] nums2 左半部分nums2[0 .. j-1] nums2 右半部分nums2[j .. n-1]只要满足两个条件i j (m n 1) / 2保证左半部分元素数不少于右半部分nums1[i-1] nums2[j]且nums2[j-1] nums1[i]保证左半部分所有元素都不大于右半部分所有元素。那么中位数就很好求了如果总长度是奇数一定是左半部分最大值如果是偶数是左半部分最大值和右半部分最小值的平均值。我用生活例子解释一下想象两副牌每副都按从小到大排列。我现在要拼出一副完整的升序大牌堆从中间把大牌堆分成两堆。只要我知道大牌堆中间左边最大的是什么、右边最小的是什么中位数就有了。而“切”的过程就是去找那个能让两边大小关系正确的分割点。3.2 为什么(m n 1) / 2是个好公式无论总长度奇偶我都希望左半部分比右半部分多一个元素或一样多。设totalLeft (m n 1) / 2对于整数除法total 5totalLeft 3左3右2左多一个total 6totalLeft 3左3右3左右相等。也就是说奇数时左半部分多出来的那一个元素就是中位数偶数时中位数是左边最大值和右边最小值的平均。这个公式把奇偶情况统一起来了。在代码中我们只在较短的数组nums1上二分搜索i然后通过j totalLeft - i自动算出第二个数组的切割位置。i的范围是[0, m]二分后自然得到唯一的合理分割。3.3 完整代码与三个边界保护public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 保证 nums1 是较短的那个数组缩短二分查找的范围 if (nums1.length nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m nums1.length, n nums2.length; int totalLeft (m n 1) / 2; int left 0, right m; while (left right) { int i (left right) / 2; int j totalLeft - i; if (i 0 j n nums1[i - 1] nums2[j]) { // 说明 i 切得太靠右a 的左半边最大元素大于 b 的右半边第一个元素 right i - 1; } else if (j 0 i m nums2[j - 1] nums1[i]) { // 说明 i 切得太靠左b 的左半边最大元素大于 a 的右半边第一个元素 left i 1; } else { // 找到了满足条件的分割点 int aLeftMax (i 0) ? Integer.MIN_VALUE : nums1[i - 1]; int aRightMin (i m) ? Integer.MAX_VALUE : nums1[i]; int bLeftMax (j 0) ? Integer.MIN_VALUE : nums2[j - 1]; int bRightMin (j n) ? Integer.MAX_VALUE : nums2[j]; if ((m n) % 2 1) { return Math.max(aLeftMax, bLeftMax); } else { return (Math.max(aLeftMax, bLeftMax) Math.min(aRightMin, bRightMin)) / 2.0; } } } return 0.0; }这里的边界保护非常关键我逐个说明当i 0时nums1左半部分是空的aLeftMax应该视为Integer.MIN_VALUE相当于“负无穷”不会干扰Math.max的结果。当i m时nums1右半部分是空的aRightMin应该视为Integer.MAX_VALUE相当于“正无穷”不会干扰Math.min的结果。二分条件里j n和i m是为了防止访问不存在的数组位置。例如j可能等于n此时nums2[j]越界需要短路退出。3.4 为什么要强制“对较短的数组二分”有两方面考虑。一是时间复杂度。i的范围是[0, m]二分的复杂度是 O(log m)所以m越小越快。如果nums1有 1000 个元素、nums2有 100 万个对 1000 那个做二分代价只有 10 次左右。二是正确性。j totalLeft - i必须落在[0, n]范围内。如果我在更长的数组上二分短数组的j totalLeft - i可能变成负数或超过n公式就不成立了。先交换确保m nj的边界才自动安全。4. 两种解法对比与“有序数据处理”的延伸4.1 一张表看懂两种解法的差异对比维度二分排除法getKth划分数组法核心思想每次排除掉 K/2 个不可能元素寻找左右两边元素数量与大小关系都满足的分割点时间复杂度O(log(mn))O(log(min(m,n)))空间复杂度O(1)O(1)代码量约40行逻辑直接约45行边界条件多调试难度较低容易局部验证较高边界写错容易死循环面试推荐度高思路通用高展示对二分搜索的深刻理解我个人倾向在面试中先说“二分排除法”因为它的推导过程更直观不容易卡壳。等面试官追问“能不能再优化”时再补上划分数组法。两种方法不是对立关系后者本质上是前者的变体只是从“排除”变成了“划分”。4.2 如果题目变成链表版本思路要转变标题里写着“数组/链表操作”很多同学会问nums1和nums2如果是链表呢链表的麻烦在于无法 O(1) 随机访问二分法的根基没了。找两个有序链表的中位数常规做法是归并复杂度 O(mn)。如果是单个链表找中点则可以用快慢指针快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中点。这个对比很有意义。它提醒我们所谓“算法”不只是记住模板而是要针对数据结构的特点选择操作方式。数组支持随机访问二分才成立链表只能顺序访问快慢指针才是它的主场。顺带一提热词里那些“链表遍历、链表插入、单链表逆序”的操作本质上都是对链表“只能逐节点访问”这个特性的应对。理解了这一点再看本题目里的数组二分你的知识结构才算真正串起来。4.3 这道题可以迁移到哪些实际场景“两个正序数组找中位数”不是一道孤立的面试题。我列几个实际场景你就知道它的价值了日志系统分位点统计假设你有两份按时间排序的日志需要计算整体耗时的 P50、P90。如果数据量太大不能合并就得分治定位。数据库查询优化针对多个有序索引段求全局中间位置的记录类似这里的二分排除。数据流中的中位数如果数据源源不断进来就不能用这道题的双数组模型而要改用两个堆大顶堆小顶堆维护。这道题是理解“静态有序集合中求中位数”的基础数据流版本是它的动态扩展。所以别把刷题当背题。每道题背后都是一个可迁移的套路有序 → 尝试二分中位数 → 尝试转化为第K小第K小 → 每次排除一半。5. 常见问题与避坑清单5.1 边界条件速查表我整理了一份问题排查对照表这些都是我写代码时真实踩过的坑症状原因解决办法返回 0.0两个数组都为空代码没处理面试时先确认约定一般题目保证至少一个非空数组下标越界i k/2直接超过数组长度用Math.min(i half, m)先截断结果差 0.5奇数/偶数分支处理错误统一用total / 2和total / 2 1两值求平均划分数组法中死循环left right时i没有正确收敛检查两个越界条件的分支方向必要时打印i和j观察nums1[i - 1]访问报错i 0时未做空左半部分处理用Integer.MIN_VALUE替代大数据量下结果溢出(left right)可能超过 int 上限用left (right - left) / 2或(left right) 15.2 我实际调试中的几条经验写这道题我建议你完完整整地把两个版本的代码都手写一遍然后跑这一组测试用例[1,3] 和 [2] → 2.0 [1,2] 和 [3,4] → 2.5 [] 和 [1] → 1.0 [1] 和 [] → 1.0 [1,1] 和 [1,1] → 1.0 [1,3,5,7,9] 和 [2,4,6,8,10] → 5.5这组用例里的[]空数组、全相等数组、奇偶长度组合几乎能覆盖所有边界情况。我自己的调试体会是不要一上来就调边界先在纸上模拟一轮“K5”的完整流程把每次排除的元素和 K 的变化写下来。只要你亲手走通一个例子代码里newI和newJ的设计逻辑就清楚了。反之直接对着代码改下标越改越乱。5.3 面试中容易被追问的几个点面试官不会只满足于“你会写”他大概率会顺着往下问“如果其中一个数组特别小另一个特别大有什么影响”——这正是为什么要对短数组二分的动机。“能不能把这个方法推广到求第 K 小的数”——完全可以getKth本身就是通用函数。“如果两个数组长度加起来是偶数中位数为什么取平均”——回到定义。“为什么nums1[i-1] nums2[j]时不用再比较nums2[j-1] nums1[i]”——因为二分过程中两边互相牵制i移动后另一侧自然满足理解这一点能避免写重复判断。我在面试别人时最怕听到候选人背代码。你只要能把O(log(mn))为什么成立讲清楚比默写十遍代码都有用。6. 最后分享一点我的个人习惯关于这道题我想以实际经验收尾。我最初学这道题时总想着把两种解法的代码都背下来结果没过多久就忘光了。后来我换了一种方式把“第 K 小排除法”当成一种套路来记把“每个数组成员都取 K/2 位置做比较”这个画面刻在脑子里遇到任何有序数组相关的题目都能自然套用。朋友跟我讨论算法时经常说最难的不是写对而是“想不到”。我觉得像“两个有序数组找中位数”这种题核心就是给你一个思维范式有序集合里找特定位置的数优先想二分每次排除一半。一旦你把这个范式内化了它就不只是一道题的答案而是一种解决问题的底层的思维习惯。我自己在之后处理生产环境的日志分位点统计时就参考了这个思路。数据按时间分片存储每个分片内部有序求全局 P95 时我用类似排除法的方式逐步缩小候选区间把原来几分钟的全量聚合降到了秒级。所以说这道题刷的值不值不在于你背了多少行代码而在于你有没有真正理解“为什么可以一次次排除一半”。理解了这一层它给你带来的收益将远超中位数本身。
我一开始接触这道题的时候觉得它就是个简单的“归并排序取中间值”问题不就是把两个数组合并起来然后按下标取值吗直到我读到题目里那个O(log(mn))的时间复杂度要求才意识到事情没那么简单。这道题是数组二分操作里非常经典的一道也是常被拿来考“你是不是真懂二分搜索”的试金石。无论你是在准备算法面试还是日常写业务代码时遇到“两份有序数据求整体分位点”的需求这套思路都用得上。所谓“寻找两个正序数组的中位数”说白了就是给定两个从小到大排好的数组把两者看成一个整体后找出这个整体序列中间位置的数值。看起来朴素但难点全在那句“对数级时间复杂度”上。这篇我会把两种主流解法都拆开讲透一种是“第 K 小元素”的排除法一种是“划分数组”切割法并附上完整的实现代码、边界处理说明和一份避坑清单。1. 题目拆解标题里藏着的三个关键词1.1 “正序数组”意味着什么先聊“正序”。这俩字是整个题目的信息红利所在。如果一个数组是无序的你找中位数最快也得先排序O(n log n)起步。但只要数组有序你就可以用二分查找、双指针这类“利用位置信息”的手段把搜索范围成半点地缩小。这也是我在实际工作中非常依赖的直觉有序数据是无价的。无论是数据库索引、日志时间序列还是接口返回的已排序列表遇到这类数据第一步不是遍历而是先想想“能不能二分”。本题目里的两个正序数组就是给你两块积木让你通过位置比较来快速收敛答案。1.2 “中位数”的本质是第 K 小的数很多同学一上来就纠结奇偶性其实完全没必要。中位数的定义可以统一成一句话在长度为total的有序序列里中位数是第total/2 1个元素奇数情况或者第total/2和第total/2 1个元素的平均值偶数情况。所以这道题本质上可以转化为一个更通用的子问题两个正序数组中如何找第 K 小的数。一旦你写出了getKth函数中位数不过就是调用它两次取平均而已。总长度 total m n 若 total 为奇数中位数 第 (total/2 1) 小的数 若 total 为偶数中位数 (第 total/2 小的数 第 (total/2 1) 小的数) / 2举个例子nums1 [1, 3]nums2 [2]total 3。我们需要第3/2 1 2小的数合并后是[1, 2, 3]第2小是2中位数就是2。而nums1 [1, 2]nums2 [3, 4]total 4需要第2小和第3小的平均数也就是2和3的平均值2.5。1.3 为什么复杂度要求是 O(log(mn))如果允许O(mn)代码五分钟就能写完双指针归并走到中间两格取平均。但题目要求的O(log(mn))直接把这条路堵死了。这个复杂度恰恰暴露了出题人的真实意图它不满足于“你会写循环”它想考的是“你懂不懂排除一半”。log(mn)级别的算法每轮操作必须能丢掉大约一半的候选元素。这就逼着你想能不能像二分查找那样每次比较两个数组中的某个位置然后一次性排除掉不可能包含答案的那一片区域答案是肯定的。这也是整道题最核心的思维跳跃点。2. 解法一二分排除法每次丢掉一半2.1 先把问题转化成“找第 K 小的数”二分排除法也叫“第K小排除法”的思路非常直白既然要在两个有序数组中找第K小的数那我每次就设法排除掉K/2个候选元素让K不断减小。当 K 缩小到 1 时问题就变得极其简单两个数组剩余部分的最小值就是答案。我可以用一个例子把流程走一遍。假设nums1 [1, 3, 5, 7, 9] nums2 [2, 4, 6, 8, 10] K 5第一轮K/2 2。比较nums1的第2个元素3和nums2的第2个元素4。因为3 4那么nums1的前2个元素1, 3绝对不可能是全局第5小的元素——原因是比它们小的元素最多只有nums1里的1个和nums2里的1个合计最多3个。所以这2个元素可以直接丢掉。K 变成5 - 2 3。第二轮两个数组的剩余部分分别是nums1 [5, 7, 9]和nums2 [2, 4, 6, 8, 10]。K/2 1。比较第1个元素5和2。2 5丢掉nums2的第1个元素2。K 变成2。第三轮剩余部分是nums1 [5, 7, 9]nums2 [4, 6, 8, 10]。K/2 1。比较5和44 5丢掉4。K 变成1。此时K等于1直接返回两个数组剩余的最小值即min(5, 6) 5。我们验证一下两个数组合并后是[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]第5小的数确实是5。2.2 为什么比较 K/2 位置是合理的你可能会问为什么选K/2而不是选K/3或者别的核心原因是想要在 O(logK) 内完成每轮都要把 K 减少固定的比例而选 K/2 是最自然、最好写的比例。细想一层如果nums1[K/2 - 1] nums2[K/2 - 1]说明nums1的前 K/2 个元素中任意一个元素x在另一个数组里能找到多少个比x小的元素最坏情况下nums2的前 K/2 - 1 个元素也可能全部小于x加上nums1自身排在x前面的那些元素比x小的元素总数最多也就是(K/2 - 1) (K/2 - 1) K - 2个仍然小于 K-1。换句话说这 K/2 个元素里不可能有全局第K小排除它们没有任何风险。这个“排除一定不可能是答案的元素”的手法和二分查找里“砍掉不可能区间”的本质一模一样。2.3 完整实现与边界设计下面给出我常用的Java版本用了两个索引i和j分别指向两个数组的剩余起点没有实际拷贝数组空间开销只是 O(1)。public double findMedianSortedArrays(int[] nums1, int[] nums2) { int total nums1.length nums2.length; if (total % 2 1) { return getKth(nums1, nums2, total / 2 1); } else { return (getKth(nums1, nums2, total / 2) getKth(nums1, nums2, total / 2 1)) / 2.0; } } private int getKth(int[] nums1, int[] nums2, int k) { int m nums1.length, n nums2.length; int i 0, j 0; while (true) { if (i m) { return nums2[j k - 1]; } if (j n) { return nums1[i k - 1]; } if (k 1) { return Math.min(nums1[i], nums2[j]); } int half k / 2; int newI Math.min(i half, m) - 1; int newJ Math.min(j half, n) - 1; if (nums1[newI] nums2[newJ]) { k - (newI - i 1); i newI 1; } else { k - (newJ - j 1); j newJ 1; } } }我重点说说几处边界newI和newJ为什么要用Math.min(i half, m) - 1因为k/2可能比数组剩余长度还大。比如nums1只剩 1 个元素但k 5那i half就会越界。取min的意思是我最多只能排除这个数组剩余的全部元素不能超出数组边界。排除元素数量用newI - i 1而不是直接用half。因为上面做了截断实际排除的可能比half少。比如一个数组本身只剩 3 个元素half 4你只能排除 3 个。当k 1时直接返回两个数组当前头部较小的那个。这也是递归/循环的终止条件。2.4 时间复杂度的直观证明每轮循环K 至少减半。K 的初始值是(mn)/2级别最坏情况下经过 O(log(mn)) 轮K 会降到 1。每轮只有常数次比较所以整体时间复杂度是 O(log(mn))空间复杂度 O(1)。我实际测试过这个方法在极端情况下的表现比如nums1为空、nums2长度为百万级别它也能在几十次比较内出结果远快于归并。3. 解法二划分数组法从切割的视角理解3.1 核心思想在两个数组里各自切一刀二分排除法的逻辑很“动态”每轮都在排除。另一种更符合“中位数定义”的思路是把两个数组分别切成左右两段使得左半部分的元素总数刚好等于右半部分或比右半部分多一个而且左半部分的最大值不大于右半部分的最小值。假设在nums1的第i个元素后面切一刀在nums2的第j个元素后面切一刀那么nums1 左半部分nums1[0 .. i-1] nums1 右半部分nums1[i .. m-1] nums2 左半部分nums2[0 .. j-1] nums2 右半部分nums2[j .. n-1]只要满足两个条件i j (m n 1) / 2保证左半部分元素数不少于右半部分nums1[i-1] nums2[j]且nums2[j-1] nums1[i]保证左半部分所有元素都不大于右半部分所有元素。那么中位数就很好求了如果总长度是奇数一定是左半部分最大值如果是偶数是左半部分最大值和右半部分最小值的平均值。我用生活例子解释一下想象两副牌每副都按从小到大排列。我现在要拼出一副完整的升序大牌堆从中间把大牌堆分成两堆。只要我知道大牌堆中间左边最大的是什么、右边最小的是什么中位数就有了。而“切”的过程就是去找那个能让两边大小关系正确的分割点。3.2 为什么(m n 1) / 2是个好公式无论总长度奇偶我都希望左半部分比右半部分多一个元素或一样多。设totalLeft (m n 1) / 2对于整数除法total 5totalLeft 3左3右2左多一个total 6totalLeft 3左3右3左右相等。也就是说奇数时左半部分多出来的那一个元素就是中位数偶数时中位数是左边最大值和右边最小值的平均。这个公式把奇偶情况统一起来了。在代码中我们只在较短的数组nums1上二分搜索i然后通过j totalLeft - i自动算出第二个数组的切割位置。i的范围是[0, m]二分后自然得到唯一的合理分割。3.3 完整代码与三个边界保护public double findMedianSortedArrays(int[] nums1, int[] nums2) { // 保证 nums1 是较短的那个数组缩短二分查找的范围 if (nums1.length nums2.length) { return findMedianSortedArrays(nums2, nums1); } int m nums1.length, n nums2.length; int totalLeft (m n 1) / 2; int left 0, right m; while (left right) { int i (left right) / 2; int j totalLeft - i; if (i 0 j n nums1[i - 1] nums2[j]) { // 说明 i 切得太靠右a 的左半边最大元素大于 b 的右半边第一个元素 right i - 1; } else if (j 0 i m nums2[j - 1] nums1[i]) { // 说明 i 切得太靠左b 的左半边最大元素大于 a 的右半边第一个元素 left i 1; } else { // 找到了满足条件的分割点 int aLeftMax (i 0) ? Integer.MIN_VALUE : nums1[i - 1]; int aRightMin (i m) ? Integer.MAX_VALUE : nums1[i]; int bLeftMax (j 0) ? Integer.MIN_VALUE : nums2[j - 1]; int bRightMin (j n) ? Integer.MAX_VALUE : nums2[j]; if ((m n) % 2 1) { return Math.max(aLeftMax, bLeftMax); } else { return (Math.max(aLeftMax, bLeftMax) Math.min(aRightMin, bRightMin)) / 2.0; } } } return 0.0; }这里的边界保护非常关键我逐个说明当i 0时nums1左半部分是空的aLeftMax应该视为Integer.MIN_VALUE相当于“负无穷”不会干扰Math.max的结果。当i m时nums1右半部分是空的aRightMin应该视为Integer.MAX_VALUE相当于“正无穷”不会干扰Math.min的结果。二分条件里j n和i m是为了防止访问不存在的数组位置。例如j可能等于n此时nums2[j]越界需要短路退出。3.4 为什么要强制“对较短的数组二分”有两方面考虑。一是时间复杂度。i的范围是[0, m]二分的复杂度是 O(log m)所以m越小越快。如果nums1有 1000 个元素、nums2有 100 万个对 1000 那个做二分代价只有 10 次左右。二是正确性。j totalLeft - i必须落在[0, n]范围内。如果我在更长的数组上二分短数组的j totalLeft - i可能变成负数或超过n公式就不成立了。先交换确保m nj的边界才自动安全。4. 两种解法对比与“有序数据处理”的延伸4.1 一张表看懂两种解法的差异对比维度二分排除法getKth划分数组法核心思想每次排除掉 K/2 个不可能元素寻找左右两边元素数量与大小关系都满足的分割点时间复杂度O(log(mn))O(log(min(m,n)))空间复杂度O(1)O(1)代码量约40行逻辑直接约45行边界条件多调试难度较低容易局部验证较高边界写错容易死循环面试推荐度高思路通用高展示对二分搜索的深刻理解我个人倾向在面试中先说“二分排除法”因为它的推导过程更直观不容易卡壳。等面试官追问“能不能再优化”时再补上划分数组法。两种方法不是对立关系后者本质上是前者的变体只是从“排除”变成了“划分”。4.2 如果题目变成链表版本思路要转变标题里写着“数组/链表操作”很多同学会问nums1和nums2如果是链表呢链表的麻烦在于无法 O(1) 随机访问二分法的根基没了。找两个有序链表的中位数常规做法是归并复杂度 O(mn)。如果是单个链表找中点则可以用快慢指针快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中点。这个对比很有意义。它提醒我们所谓“算法”不只是记住模板而是要针对数据结构的特点选择操作方式。数组支持随机访问二分才成立链表只能顺序访问快慢指针才是它的主场。顺带一提热词里那些“链表遍历、链表插入、单链表逆序”的操作本质上都是对链表“只能逐节点访问”这个特性的应对。理解了这一点再看本题目里的数组二分你的知识结构才算真正串起来。4.3 这道题可以迁移到哪些实际场景“两个正序数组找中位数”不是一道孤立的面试题。我列几个实际场景你就知道它的价值了日志系统分位点统计假设你有两份按时间排序的日志需要计算整体耗时的 P50、P90。如果数据量太大不能合并就得分治定位。数据库查询优化针对多个有序索引段求全局中间位置的记录类似这里的二分排除。数据流中的中位数如果数据源源不断进来就不能用这道题的双数组模型而要改用两个堆大顶堆小顶堆维护。这道题是理解“静态有序集合中求中位数”的基础数据流版本是它的动态扩展。所以别把刷题当背题。每道题背后都是一个可迁移的套路有序 → 尝试二分中位数 → 尝试转化为第K小第K小 → 每次排除一半。5. 常见问题与避坑清单5.1 边界条件速查表我整理了一份问题排查对照表这些都是我写代码时真实踩过的坑症状原因解决办法返回 0.0两个数组都为空代码没处理面试时先确认约定一般题目保证至少一个非空数组下标越界i k/2直接超过数组长度用Math.min(i half, m)先截断结果差 0.5奇数/偶数分支处理错误统一用total / 2和total / 2 1两值求平均划分数组法中死循环left right时i没有正确收敛检查两个越界条件的分支方向必要时打印i和j观察nums1[i - 1]访问报错i 0时未做空左半部分处理用Integer.MIN_VALUE替代大数据量下结果溢出(left right)可能超过 int 上限用left (right - left) / 2或(left right) 15.2 我实际调试中的几条经验写这道题我建议你完完整整地把两个版本的代码都手写一遍然后跑这一组测试用例[1,3] 和 [2] → 2.0 [1,2] 和 [3,4] → 2.5 [] 和 [1] → 1.0 [1] 和 [] → 1.0 [1,1] 和 [1,1] → 1.0 [1,3,5,7,9] 和 [2,4,6,8,10] → 5.5这组用例里的[]空数组、全相等数组、奇偶长度组合几乎能覆盖所有边界情况。我自己的调试体会是不要一上来就调边界先在纸上模拟一轮“K5”的完整流程把每次排除的元素和 K 的变化写下来。只要你亲手走通一个例子代码里newI和newJ的设计逻辑就清楚了。反之直接对着代码改下标越改越乱。5.3 面试中容易被追问的几个点面试官不会只满足于“你会写”他大概率会顺着往下问“如果其中一个数组特别小另一个特别大有什么影响”——这正是为什么要对短数组二分的动机。“能不能把这个方法推广到求第 K 小的数”——完全可以getKth本身就是通用函数。“如果两个数组长度加起来是偶数中位数为什么取平均”——回到定义。“为什么nums1[i-1] nums2[j]时不用再比较nums2[j-1] nums1[i]”——因为二分过程中两边互相牵制i移动后另一侧自然满足理解这一点能避免写重复判断。我在面试别人时最怕听到候选人背代码。你只要能把O(log(mn))为什么成立讲清楚比默写十遍代码都有用。6. 最后分享一点我的个人习惯关于这道题我想以实际经验收尾。我最初学这道题时总想着把两种解法的代码都背下来结果没过多久就忘光了。后来我换了一种方式把“第 K 小排除法”当成一种套路来记把“每个数组成员都取 K/2 位置做比较”这个画面刻在脑子里遇到任何有序数组相关的题目都能自然套用。朋友跟我讨论算法时经常说最难的不是写对而是“想不到”。我觉得像“两个有序数组找中位数”这种题核心就是给你一个思维范式有序集合里找特定位置的数优先想二分每次排除一半。一旦你把这个范式内化了它就不只是一道题的答案而是一种解决问题的底层的思维习惯。我自己在之后处理生产环境的日志分位点统计时就参考了这个思路。数据按时间分片存储每个分片内部有序求全局 P95 时我用类似排除法的方式逐步缩小候选区间把原来几分钟的全量聚合降到了秒级。所以说这道题刷的值不值不在于你背了多少行代码而在于你有没有真正理解“为什么可以一次次排除一半”。理解了这一层它给你带来的收益将远超中位数本身。
