2011 年第 42 题

题目描述

给定两个长度相等的升序序列 A 和 B，设计一个在时间和空间两方面都尽可能高效的算法，找出这两个序列整体的中位数。

这里的“中位数”指合并后的长度为 2n 的升序序列中，第 n 个元素，也就是下中位数。

解题思路

最优做法不是把两个数组完整合并，而是利用二分思想不断舍弃不可能包含中位数的一半区间。

设当前考虑的子数组分别为：

• A[low1..high1]
• B[low2..high2]

每次取它们各自的中位数 m1 和 m2：

• 若 m1 == m2，答案就是它。
• 若 m1 < m2，则 A 的左半部分和 B 的右半部分中至少有一半元素不可能成为最终中位数，可同时舍弃。
• 若 m1 > m2，则反过来舍弃 A 的右半部分和 B 的左半部分。

区间长度不断减半，直到每个数组只剩一个元素，答案就是二者较小值。

手算示例

A = [11, 13, 15, 17, 19]

B = [2, 4, 6, 8, 20]

第一次：
A 中位数 = 15
B 中位数 = 6
15 > 6

舍弃 A 的右半和 B 的左半后，保留：
A = [11, 13, 15]
B = [6, 8, 20]

第二次：
A 中位数 = 13
B 中位数 = 8
13 > 8

继续缩小：
A = [11, 13]
B = [8, 20]

第三次：
A 中位数 = 11
B 中位数 = 8

最后保留到单元素阶段，可得答案为 11

Python 实现

def median_two_sorted_equal_len(a, b):
    """
    a, b 为两个等长升序数组，返回合并后的下中位数
    """
    n = len(a)
    if n == 0 or n != len(b):
        raise ValueError("a 和 b 必须是等长非空数组")

    low1, high1 = 0, n - 1
    low2, high2 = 0, n - 1

    while low1 < high1:
        mid1 = (low1 + high1) // 2
        mid2 = (low2 + high2) // 2
        offset = ((high1 - low1 + 1) % 2 == 0)

        if a[mid1] == b[mid2]:
            return a[mid1]
        if a[mid1] < b[mid2]:
            low1 = mid1 + (1 if offset else 0)
            high2 = mid2
        else:
            high1 = mid1
            low2 = mid2 + (1 if offset else 0)

    return min(a[low1], b[low2])

复杂度分析

• 时间复杂度：O(log n)
• 空间复杂度：O(1)

易错点

• 真题求的是下中位数，不是平均值。
• 偶数长度区间缩小时，端点是否加一要分奇偶讨论。
• 不要写成完整归并的 O(n) 做法，虽然能做对，但不是题目追求的最优思想。

对应题

来源	题目	相似度	主要差异
LeetCode	4. 寻找两个正序数组的中位数	70%	该题返回平均值，真题返回下中位数
PAT 甲级	1029 Median	75%	真题为两个等长序列
《算法导论》	9.3-8 / 9.3-10	90%	问题模型基本一致

难度

⭐️⭐️⭐️⭐️⭐️