★ FEATURED ARTICLE 刷数据结构题最怕遇到那种看着有思路、写出来却到处是 bug 的题目求两个升序序列的中位数就是典型代表。单独看一个有序数组中位数一句话就能说清两个升序序列拼在一起很多人的第一反应是先合并成一个数组再按下标取。这个思路没错但会错过归并排序里真正值钱的东西。这篇笔记记录的是我从最笨的合并法一路优化到二分切分法的完整过程适合正在复习数据结构、准备算法面试或者想把归并排序思想用熟的人。下面三种方法复杂度从 O(mn) 空间一路降到 O(1) 空间最后二分法能做到 O(log min(m,n))每一层都能看到不同的算法思维。1. 先别急着写代码把中位数的定义想清楚1.1 中位数不是单纯“中间那个数”单个有序数组的中位数大家都会求长度为奇数取正中间那个长度为偶数取中间两个的平均值。两个升序序列的中位数本质上也是把两个数组当成一个合并后的整体再按同样的规则取。比如 A [1, 3, 5, 7]B [2, 4, 6, 8, 10]合并后整体是 [1, 2, 3, 4, 5, 6, 7, 8, 10]总长度 9中位数就是第 5 个元素也就是 5。这里最容易被忽略的是中位数不一定来自某一个固定的数组可能来自 A也可能来自 B完全取决于两个数组元素穿插后的位置。所以我在写任何解法前都会先把两个总长度公式写在草稿纸上总长度 total m n。total 为奇数时合并后下标 total / 2 的元素就是中位数0-based。total 为偶数时合并后下标 total / 2 - 1 和 total / 2 的两个元素取平均值。别小看这两行后面无论双指针还是二分切分循环边界全靠它们撑住。很多人代码写错不是算法思路错而是“第几个”和“下标几号”换算错了。1.2 两个升序序列到底藏了什么信息这道题最关键的前提是“两个序列各自升序”。如果数组是乱序的那除了全部排序基本没有更好的办法复杂度至少是 O((mn) log(mn))。但既然各自有序我们就有了两个可利用的点第一可以直接用归并排序里的 merge 过程把两个有序序列变成一个新的有序序列这一步是线性的不需要再整体排序。第二既然知道整体是有序的中位数其实只依赖于整体序列中间位置的少数几个元素很多中间过程可以忽略于是才有了后面的双指针和二分优化。我习惯把这个信息点理解成“题目已经送你一半答案了”有序性让你不用比较所有元素只需要在边界处验证几个关键位置之间的关系。这个想法也是第三种二分切分方法的理论基础。2. 方法一归并排序里的 merge 就是为这个场景准备的2.1 把两个有序序列合并成一个有序序列归并排序大家都不陌生先把数组拆成两半递归排序最后再用 merge 把两个有序数组合并。很多笔记会把归并排序的递归部分讲得很细但 merge 这个函数本身才是真正的核心。它做的事情很简单两个指针分别指向两个有序数组的头部比较当前指到的元素谁小谁先放入结果数组然后对应指针后移。求两个升序序列的中位数恰好就是这个场景。你不需要对整个大数组排序只需要把两个已经有序的序列线性合并到一起合并完成后的数组就是最终有序的整体。这时候取中位数的下标问题就解决了。我第一次刷这道题时就是用的这个思路把归并排序里的 merge 函数原封不动搬出来先得到一个完整的有序数组再按奇偶情况取中间值。代码写起来非常直观几乎不会出逻辑错误非常适合用来验证自己对归并过程的理解。2.2 完整实现合并后直接按下标取中位用 C 写出来大概是这样的#include vector #include algorithm using namespace std; vectorint mergeTwoSorted(const vectorint a, const vectorint b) { int i 0, j 0; int m a.size(), n b.size(); vectorint c; c.reserve(m n); while (i m j n) { if (a[i] b[j]) { c.push_back(a[i]); } else { c.push_back(b[j]); } } while (i m) c.push_back(a[i]); while (j n) c.push_back(b[j]); return c; } double medianOfTwoSorted1(const vectorint a, const vectorint b) { vectorint c mergeTwoSorted(a, b); int total c.size(); if (total % 2 1) { return c[total / 2]; } return (c[total / 2 - 1] c[total / 2]) / 2.0; }注意两个细节c.reserve(m n)可以提前分配好内存减少 vector 扩容带来的开销。偶数情况一定要除以2.0不是2否则结果是整数小数部分直接被截掉。我一开始写过/2结果测试用例 [1, 2, 3, 4] 和 [5, 6] 时正确中位数 3.5 被算成了 3。这种错很隐蔽因为有些用例恰好是整数结果你会以为是正确的。2.3 复杂度与适用场景方法一的时间复杂度是 O(mn)因为要遍历两个数组各一次空间复杂度是 O(mn)因为额外创建了一个完整的结果数组。如果 mn 是百万级别内存开销就会比较明显。它的优点也很突出思路最直白归并排序的 merge 函数直接复用。边界问题少只要 merge 写对取中位数就只是下标计算。适合快速验证答案也适合帮助初学者理解归并过程。缺点则是“杀鸡用了牛刀”。我们明明只想取中间一两个元素却把整个数组都构造了出来。如果面试官只是问你能不能再优化这个问题就来了。所以方法一可以作为铺垫但通常不是最终答案。3. 方法二双指针只数到中位不用真的合并3.1 把 merge 过程中的“中间两个值”记下来方法一之所以浪费空间是因为结果数组里中位数以外的元素暂时都用不到。但仔细想一下中位数只依赖整体序列中间的一两个位置。我们完全可以模拟 merge 的过程用两个指针从左往右比较直到走到中位数所在的位置同时把上一个元素也记下来用于偶数情况求平均。这个方法其实就是方法一的“惰性版本”指针移动的规则和 merge 完全一样只是不把每次选中的元素存进数组而是只在变量里滚动保留前一个值和当前值。等循环结束时根据 total 的奇偶返回结果。我把它理解成“边归并边报数”两个队伍按顺序从小到大排好你从队头开始喊数喊到中间那个位置就停下。不需要知道所有队员的名字只需要记住刚才喊到的两个编号。3.2 双指针代码与边界判断实现如下double medianOfTwoSorted2(const vectorint a, const vectorint b) { int m a.size(), n b.size(); int total m n; int i 0, j 0; int prev 0, cur 0; for (int step 0; step total / 2; step) { prev cur; if (i m (j n || a[i] b[j])) { cur a[i]; } else { cur b[j]; } } if (total % 2 1) { return cur; } return (prev cur) / 2.0; }这里最关键的是if (i m (j n || a[i] b[j]))这个判断。很多人会直接写a[i] b[j]但在其中一个数组已经遍历完时继续访问a[i]或b[j]就会越界。正确写法需要先判断i m同时用j n表示 b 数组已经走完此时只能取 a 的当前元素。另一个容易出错的地方是循环次数。step total / 2实际上会执行total / 2 1次对应 0-based 下标total / 2。比如 total 5中位数下标是 2需要取到第 3 个元素循环 3 次没错。total 6中位数是下标 2 和 3 的平均循环 4 次最后一次的prev正好是下标 2cur是下标 3。3.3 空间省下来了但代码变“脏”了一点方法二的时间复杂度仍然是 O(mn)但空间复杂度降到了 O(1)只用了两个临时变量。代价是逻辑没有方法一那么直白尤其偶数情况下要明白prev的更新时机。我调试时最多的问题出现在把prev cur放在循环最后而不是下一次循环的开头。这会导致奇数没问题偶数求平均时prev还是初始化时的 0。正确做法是每次取新元素之前先把旧值保存下来。这一步一旦写对方法二的正确率就会很高。这个方案足够应对大多数笔试场景代码短思路简单空间利用率高。如果面试官没有明确要求优化到对数级别写出方法二通常已经不错了。但如果你想展示分治思维就要继续看第三种。4. 方法三二分查找切分点对数时间的中位数解4.1 换一个角度看中位数中位数除了“中间那个数”之外还有一个更本质的理解把合并后的有序序列切成左右两半左边元素数量要么等于右边要么比右边多一个。如果这个切分点找对了中位数就只取决于切分点左右两侧的少数几个元素。现在的问题变成了两个有序数组不合并我能不能直接找到这个切分点答案是可以。具体做法是在较短的数组上二分确定从它左边取多少个元素然后根据左半部分总数量自动算出另一个数组的左边要取多少个元素。可以想象有两列已经按身高排好的队伍要把它们合成一列并从中间切开。原来两列分别有序你不需要把所有人数一遍只需要在每列各选一个切点保证切点左侧的所有人都比右侧的所有人矮就行。4.2 确定二分区间和 j 的计算方式设 A 是较短的数组长度 mB 是较长的数组长度 n且 m n。中位数的左侧元素个数记为 leftCount (total 1) / 2这里 total m n(total 1) / 2是向上取整后的左半部分数量。假设在 A 中左侧取 i 个元素那么 B 中左侧就必须取 j leftCount - i 个元素。i 的取值范围是 [0, m]因为 A 最多只能把 m 个元素全部放在左侧。为什么一定要在较短数组上二分因为 i 的范围越小二分次数越少复杂度是 O(log min(m,n))。另一方面m n 时 j 会自动落在 [0, n] 范围内省掉很多额外判断。切分点合法的条件有两个A[i-1] B[j]即 A 左边的最后一个元素不能大于 B 右边的第一个元素。B[j-1] A[i]即 B 左边的最后一个元素不能大于 A 右边的第一个元素。如果 A[i-1] B[j]说明 A 拿进左侧的元素太多了i 要向左移动否则说明 i 还可以向右移动让左侧包含更多 A 的元素。这两个条件为什么够用因为 A 和 B 内部各自有序所以 A 左侧的所有元素都 A[i-1]B 右侧的所有元素都 B[j]加上跨数组的两个临界条件就能证明左半部分整体都小于等于右半部分。4.3 完整代码与边界值处理边界处理是方法三最容易出错的地方。如果 i 0表示 A 左侧一个元素都不取A[i-1] 不存在应该视为负无穷如果 i m表示 A 全部在左侧A[i] 不存在应该视为正无穷。B 同理。#include vector #include climits #include algorithm using namespace std; double medianOfTwoSorted3(vectorint a, vectorint b) { const vectorint A (a.size() b.size()) ? a : b; const vectorint B (a.size() b.size()) ? b : a; int m A.size(), n B.size(); int total m n; int leftCount (total 1) / 2; int low 0, high m; while (low high) { int i low (high - low) / 2; int j leftCount - i; int aLeft (i 0) ? INT_MIN : A[i - 1]; int aRight (i m) ? INT_MAX : A[i]; int bLeft (j 0) ? INT_MIN : B[j - 1]; int bRight (j n) ? INT_MAX : B[j]; if (aLeft bRight bLeft aRight) { if (total % 2 1) { return max(aLeft, bLeft); } return (max(aLeft, bLeft) min(aRight, bRight)) / 2.0; } else if (aLeft bRight) { high i - 1; } else { low i 1; } } return -1.0; }这里我用了const vectorint A和const vectorint B来引用较短和较长的数组没有额外复制数据所以空间复杂度依然是 O(1)。如果这时候图省事直接按值传参vectorint a复制两个数组本身就会把时间拖回 O(mn)就谈不上对数复杂度了。奇数情况下leftCount 比右侧多一个中位数就是左半部分的最大值max(aLeft, bLeft)。偶数情况下左半部分和右半部分数量相等中位数是max(aLeft, bLeft)和min(aRight, bRight)的平均值。4.4 为什么这个方法是对的有人会担心只检查四个边界值会不会漏掉中间位置无序的情况不会。A 和 B 内部各自有序所以A 左侧的任意元素小于等于 A[i-1]A[i-1] 小于等于 B[j]所以 A 左侧所有元素小于等于 B[j] 及其右侧所有元素B 左侧的任意元素小于等于 B[j-1]B[j-1] 小于等于 A[i]所以 B 左侧所有元素小于等于 A[i] 及其右侧所有元素。这两条合起来左侧整体一定小于等于右侧整体。也就是说你虽然只是在边界处做了四次比较但借助“内部有序”这个前提实际上已经验证了整个切分的合法性。二分只是用来寻找这个合法切分点一旦找到中位数立刻就能算出来。我一开始看到这个解法觉得像是变魔术后来自己画了好几组用例把 i 从 0 到 m 都列出来手动模拟切分后的左右数组才真正说服自己。理解这个解法的关键不是背代码而是画图把 A 和 B 上下对齐中间画一条竖线竖线左侧元素数固定再看四个边界值是否满足大小关系。5. 三种方法横向对比时间、空间、代码量怎么权衡5.1 复杂度对照表把三种方法放在同一个表里看会更清楚方法时间复杂度空间复杂度代码难度易错点归并合并数组O(mn)O(mn)低偶中位数除以 2.0双指针滚动变量O(mn)O(1)中低越界判断、prev 更新时机二分切分数组O(log min(m,n))O(1)较高边界 INT_MIN/INT_MAX、i 的二分方向面试时如果要求手写完整可运行的代码方法二通常是性价比最高的选择既没有方法一的空间浪费又没有方法三的大量边界条件。我自己在笔试模拟时也经常优先写方法二因为它的代码量只有十几行出错概率低。但如果面试官追问“还能不能更快”或者题目数据量极大比如 m 和 n 都到 1e9 级别那么 O(mn) 的时间就无法接受必须用方法三。这时候考察的就是你对“中位数定义”的理解程度而不仅是编码能力。5.2 不同场景怎么选我把选择逻辑整理成几条经验如果在复习归并排序方法一值得完整写一遍重点体会 merge 过程。如果是笔试或线上测评优先写方法二不要一上来就啃二分切分。如果是为了准备算法面试方法三是必须掌握的因为它是经典的分治优化模型。如果只是想验证某个复杂解法是否正确可以用方法一当“暴力对拍器”用随机数组测试方法三的输出是否一致。我实际练习时常用一个小技巧写一个暴力解法再写一个优化解法在一个循环里生成随机数组不断比较结果。这个方法能快速暴露二分切分的边界问题比背测试用例高效得多。5.3 归并排序的思维起点merge 只是第一步回到标题里的那句话“归并排序你会用了吗”很多人刷过归并排序但只记住了递归拆分数组的步骤忘了 merge 函数才是整个算法最有复用价值的部分。求两个升序序列的中位数本质上就是一次 merge 过程的变体。双指针法就是 merge 的惰性版本二分切分法则是 merge 的“整体跳过”版本。理解了这一点你会看到归并排序并不只是一段需要背的代码而是一种“合并有序结构”的思路。之后的链表排序、逆序对计数、甚至外部排序里的多路归并全都是同一套思想的扩展。所以这道题表面上在求中位数实际上是在检验你对有序序列合并的理解程度。6. 调试记录这些边界坑我基本都踩过6.1 典型错误与排查快查表下列问题是我在练习和帮别人 review 代码时反复遇到的直接总结成一张排查表错误现象可能原因解决办法偶中位数结果缺小数除以了整数 2改为除以 2.0双指针数组越界没判断一个数组已遍历完条件写 i m (j n奇数长度结果不正确循环次数少了 1 次用step total / 2二分切分找不到答案没选较短数组进行二分先保证 m n取 A[i] 或 B[j] 越界没有处理 i m / j n用 INT_MAX 替代CONTINUE 返回值异常循环结束后强制返回合法解一定存在返回只是兜底防警告二分切分里最容易搞混的是调整方向当 A[i-1] B[j] 时说明 A 左侧取多了应该缩小 i也就是把 high 调到 i-1反过来当 B[j-1] A[i] 时说明 A 左侧取少了应该增大 ilow 调到 i1。我自己会因为“左边太大”和“i 太大”之间绕晕后来干脆固定记一句话哪边左边的最后一个元素太大就往相反方向收缩。6.2 建议准备的一组测试用例无论用哪种方法写完后我都建议跑下面这些边界用例覆盖空数组、奇偶长度、相等元素、一长一短等典型情况A []B [1]结果 1。A [1, 3]B [2]结果 2。A [1, 2]B [3, 4]结果 2.5。A [1, 3, 5, 7]B [2, 4, 6, 8]结果 4.5。A [1, 2, 3, 4]B []结果 2.5。A [1, 1]B [1, 1]结果 1。A [100]B [1]结果 50.5。特别注意最后一组两个数组各只有一个元素合并后中位数是两者的平均值。很多人在二分切分里会忽略这种两个数组长度都极小的情况导致 leftCount 和 j 的映射对不上。6.3 我自己的做题习惯最后分享一个我自己形成的小习惯看到“两个有序序列”组合求某个统计量时先不着急写暴力排序而是问自己三个问题能不能用归并的线性推进能不能只保留中间值能不能用二分跳过一半元素。这个思考框架其实是从这道题里提炼出来的后来遇到合并有序链表、求两个有序数组的第 k 小元素、寻找交集等题目我都沿用了同一套思路。二分切分法的代码第一次写容易劝退但只要你把边界条件一个个跑过后面就会越用越顺。我现在看到求两个升序序列的中位数的题目已经不需要犹豫直接在脑子里画出切分线对着四个边界值做判断就够了。这种熟练程度靠的并不是死记硬背而是把归并、双指针、二分这三种层级都亲手写过一遍之后的自然结果。
阅读完成 · 觉得有帮助？
