题目描述
思路解析
一句话答案：LeetCode 4 寻找两个正序数组的中位数用双指针归并：两边本来就有序，每轮比两个头取较小的往前推，一趟拉链式合并到正中间就是中位数，时间 O(m+n)、空间 O(m+n)。
两串各自有序，合起来的正中间是哪个数
给两个各自从小到大排好的数组 A 和 B，把它们合起来看成一整串，求正中间那个数，也就是中位数（所有数排好序后站在最中央的那个；总个数是偶数、没有单独一个正中时，取挨着中间的两个数求平均）。题面 A=[1,3,8,12]、B=[2,7,9,10,15]，合起来 9 个排好是 [1,2,3,7,8,9,10,12,15]，正中间第 5 个是 8，答案就是 8。
拼一起再整体排序，白付的是哪一笔
把 A、B 拼成一个大数组、再从头到尾整体排一次序取正中间，这条路要 O((m+n)log(m+n))（m、n 是两数组长度，大 O 记号衡量数据变大时操作量的放大速度）。排序里那个 log 因子是白花的——A、B 本来各自已经有序，拼一起重排等于把这张现成的牌撕了重发。
两边各自排好，一次只需比两个头
两个数组都已经有序。想象两只手分别按在 A、B 的开头，谁的当前头小，接下来该进合并结果的最小数就一定是它——它比自己身后的都小、也比对方的头小，全局没有更小的了。取走它、那只手往后挪一格，再比新的两个头。像拉链一样一格格咬合，一趟扫下来两串就并成一整串有序数组，这就是双指针归并（两个指针各扫一边、边比边合）。
一只手先走完怎么办，中位数又落在哪个下标
走起来是这样：两个指针 i、j 各指 A、B 的头，每轮比 A[i] 和 B[j]，把较小的接进合并数组、对应指针前移，相等时接谁都行。循环到某一只手先走完——比如 A 全取光了，B 剩下那截本来就有序，直接整段接到尾巴上。合并数组凑齐后看它的长度 n：n 是奇数，正中只有一个，取下标 n//2（下标从 0 数起）；n 是偶数，正中是挨着的两个，取下标 n//2−1 和 n//2 两数求平均。
两串归并到第 5 个数，一步步看
i、j 都从 0 起。A[0]=1 ≤ B[0]=2，接 1，i 到 1；A[1]=3 比 B[0]=2 大，接 2，j 到 1；A[1]=3 ≤ B[1]=7，接 3，i 到 2；A[2]=8 比 B[1]=7 大，接 7，j 到 2；A[2]=8 ≤ B[2]=9，接 8，i 到 3；A[3]=12 比 B[2]=9 大，接 9，j 到 3；12 又比 B[3]=10 大，接 10，j 到 4；A[3]=12 ≤ B[4]=15，接 12，i 到 4。此时 A 走完，B 剩的 15 整段接上。合并数组是 [1,2,3,7,8,9,10,12,15]，长度 9 是奇数，取下标 9//2=4，正是第 5 个数 8。
归并完漏接剩下那截，尾巴上的数就没了
复杂度上，i、j 加起来把 A、B 各扫一遍、共 m+n 步，时间 O(m+n)；额外开一个合并数组装结果，空间 O(m+n)。几个容易栽的地方：那个 while 只在两手都没走完时才转，必有一只先停，另一只剩的那截忘了接上，尾部的数会整片丢失。中位数别一律拿 n//2 收口，那只对奇数长度成立，偶数长度得取中间两数求平均，漏了会少算一个数。某个数组为空则一次循环都不进，非空那串整段接上就退化成单个有序数组取中位数，照样对、不必特判。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住归并的核心：比较两个数组当前的头，谁小取谁。合并出的数组从小到大排好，正中间就是中位数。
下方这排格子是归并后会得到的有序数组，现在还没确定（变暗）。指针 ai、bi 分别站在 A、B 的开头，准备逐格填充。
比较两个数组当前的头：A 这边是 1，B 这边是 2。较小的是 1，它来自 数组 A，放进第 1 格。
第 1 格定为 1（标绿表示已确定）。对应指针前移，继续比较下一对。
比较两个数组当前的头：A 这边是 3，B 这边是 2。较小的是 2，它来自 数组 B，放进第 2 格。
第 2 格定为 2（标绿表示已确定）。对应指针前移，继续比较下一对。
比较两个数组当前的头：A 这边是 3，B 这边是 7。较小的是 3，它来自 数组 A，放进第 3 格。
第 3 格定为 3（标绿表示已确定）。对应指针前移，继续比较下一对。
比较两个数组当前的头：A 这边是 8，B 这边是 7。较小的是 7，它来自 数组 B，放进第 4 格。
第 4 格定为 7（标绿表示已确定）。对应指针前移，继续比较下一对。
比较两个数组当前的头：A 这边是 8，B 这边是 9。较小的是 8，它来自 数组 A，放进第 5 格。
第 5 格填入 8——这正好是合并后正中间的位置（总长 9 个，正中是第 5 个）。中位数就是 8，归并到这里就能停了。
比较两个数组当前的头：A 这边是 12，B 这边是 9。较小的是 9，它来自 数组 B，放进第 6 格。
第 6 格定为 9（标绿表示已确定）。对应指针前移，继续比较下一对。
比较两个数组当前的头：A 这边是 12，B 这边是 10。较小的是 10，它来自 数组 B，放进第 7 格。
第 7 格定为 10（标绿表示已确定）。对应指针前移，继续比较下一对。
比较两个数组当前的头：A 这边是 12，B 这边是 15。较小的是 12，它来自 数组 A，放进第 8 格。
第 8 格定为 12（标绿表示已确定）。对应指针前移，继续比较下一对。
A 这边已经取完了，B 剩下的本来就有序，直接把 B[4]=15 接到第 9 格。
第 9 格定为 15（标绿表示已确定）。对应指针前移，继续比较下一对。
整个归并完成，得到有序数组 [1,2,3,7,8,9,10,12,15]。一共 9 个数，正中间（第 5 个，标红）就是中位数 8。
三个高频追问：偶数长度取平均、O(log) 二分划分思路、空数组无需特判。
参考代码
def findMedianSortedArrays(A, B): merged = [] i = j = 0 # A、B 的指针 while i < len(A) and j < len(B): if A[i] <= B[j]: # 取较小的放进来 merged.append(A[i]); i += 1 else: merged.append(B[j]); j += 1 merged += A[i:] # 剩下的直接接上 merged += B[j:] n = len(merged) if n % 2: # 奇数: 正中那个 return merged[n // 2] return (merged[n//2 - 1] + merged[n//2]) / 2 # 偶数取平均复杂度
- 时间：O(m+n)，归并把两个数组各扫一遍，m、n 是两数组长度
- 空间：O(m+n)，用一个合并数组存放归并结果
易错点
面试追问把动画讲成自己的话
追问总长度是偶数时中位数怎么取？
追问归并法 O(m+n)，但面试常要 O(log(m+n))，思路是什么？
追问如果其中一个数组为空呢？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
查找元素的首末位置
LeetCode 34 · 中等 · 沿着 二分查找 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题