寻找两个正序数组的中位数 图解题解

两串各自有序，合起来的正中间是哪个数

给两个各自从小到大排好的数组 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 收口，那只对奇数长度成立，偶数长度得取中间两数求平均，漏了会少算一个数。某个数组为空则一次循环都不进，非空那串整段接上就退化成单个有序数组取中位数，照样对、不必特判。

Python

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  # 偶数取平均

C++

double findMedianSortedArrays(vector<int>& A, vector<int>& B){
    vector<int> m;
    int i = 0, j = 0;
    while (i < A.size() && j < B.size())
        if (A[i] <= B[j]) m.push_back(A[i++]);
        else m.push_back(B[j++]);
    while (i < A.size()) m.push_back(A[i++]);
    while (j < B.size()) m.push_back(B[j++]);
    int n = m.size();
    if (n & 1) return m[n / 2];
    return (m[n/2 - 1] + m[n/2]) / 2.0;
}

Java

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int[] m = new int[A.length + B.length];
        int i = 0, j = 0, k = 0;
        while (i < A.length && j < B.length)
            m[k++] = A[i] <= B[j] ? A[i++] : B[j++];
        while (i < A.length) m[k++] = A[i++];
        while (j < B.length) m[k++] = B[j++];
        int n = m.length;
        if (n % 2 == 1) return m[n / 2];
        return (m[n/2 - 1] + m[n/2]) / 2.0;
    }
}