力扣-4. 寻找两个正序数组的中位数（Median of Two Sorted Arrays）

最后编辑于2025-05-20

4. 寻找两个正序数组的中位数（Median of Two Sorted Arrays）

Hard

给定两个 有序 数组 nums1 和 nums2，大小分别为 m 和 n，请你找出这两个正序数组的中位数，并且要求总体运行时间复杂度为 O(log(m + n))。

示例 1：

输入： nums1 = [1,3], nums2 = [2]
输出： 2.00000
解释： 合并后数组为 [1,2,3]，中位数是 2。

示例 2：

输入： nums1 = [1,2], nums2 = [3,4]
输出： 2.50000
解释： 合并后数组为 [1,2,3,4]，中位数是 (2 + 3) / 2 = 2.5。

约束：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6

问题分析（关键思路）

题目要求时间复杂度为 O(log(m+n))，因此自然想到二分查找。但难点在于：如何在两个未合并的有序数组之间应用二分法？常见且直观的解决思路有三种：

  1. 二分查找「第 K 小」元素（把求中位数转成查第 k 小的问题）：

    • 设总长度为 m + n，中位数可统一用 (findKth((m+n+1)/2) + findKth((m+n+2)/2)) / 2.0 处理奇偶两种情况。
    • 关键是实现 findKth(nums1, i, nums2, j, k)：每次比较两个数组的第 k/2 个元素，较小的一方前 k/2 个元素可以被淘汰（因为它们不可能是第 k 小），然后递归/迭代继续在剩余元素里查找第 k - k/2 小。时间复杂度 O(log(m+n))（严格讲为 O(log(m+n)) 的因子取决于每次 k 减少比例），空间复杂度取决于递归深度或使用迭代 O(1)。

  2. 变体：拷贝法（不推荐，用于思路拓展）：

    • 每次通过切片构造新的子数组（复制数据），同样按 k/2 淘汰，但会发生数组拷贝，实际时间/空间成本较高，不建议在面试/工程中使用，只作思路补充。

  3. 迭代二分切分法（推荐）：

    • 将两个数组“切分”为左右两部分，要求左侧元素个数等于右侧元素个数（或相差 1），并且满足 max(left parts) <= min(right parts)，则中位数为：(max(L1,L2) + min(R1,R2)) / 2。
    • 对切分点在短数组上二分，时间复杂度 O(log(min(m, n)))，这是最常见且优雅的解法（也能很好的在面试中阐述）。

下面给出三种 C++ 实现（对应上面三类思路），并说明复杂度。

方法一：二分查找第 K 小（递归实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
    }

    int findKth(const vector<int>& nums1, int i, const vector<int>& nums2, int j, int k) {
        if (i >= (int)nums1.size()) return nums2[j + k - 1];
        if (j >= (int)nums2.size()) return nums1[i + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);

        int midVal1 = (i + k/2 - 1 < (int)nums1.size()) ? nums1[i + k/2 - 1] : INT_MAX;
        int midVal2 = (j + k/2 - 1 < (int)nums2.size()) ? nums2[j + k/2 - 1] : INT_MAX;

        if (midVal1 < midVal2) {
            return findKth(nums1, i + k/2, nums2, j, k - k/2);
        } else {
            return findKth(nums1, i, nums2, j + k/2, k - k/2);
        }
    }
};
  • 时间复杂度： O(log(m + n))（每次 k 约减半）
  • 空间复杂度： 递归栈 O(log(m + n))（可改为迭代降低栈深）

思路要点： 同时在两个数组上「按 k/2 划分」，较小一侧可以一次性淘汰 k/2 个元素，继续在剩余元素中查找第 k - k/2 小。

方法二：拷贝子数组的递归（思路拓展，不推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2.0;
    }

    int findKth(vector<int> nums1, vector<int> nums2, int k) {
        if (nums1.empty()) return nums2[k - 1];
        if (nums2.empty()) return nums1[k - 1];
        if (k == 1) return min(nums1[0], nums2[0]);

        int i = min((int)nums1.size(), k / 2);
        int j = min((int)nums2.size(), k / 2);

        if (nums1[i - 1] > nums2[j - 1]) {
            // 丢弃 nums2 的前 j 个元素
            return findKth(nums1, vector<int>(nums2.begin() + j, nums2.end()), k - j);
        } else {
            // 丢弃 nums1 的前 i 个元素
            return findKth(vector<int>(nums1.begin() + i, nums1.end()), nums2, k - i);
        }
    }
};
  • 时间复杂度： 理论上与方法一类似，但因为每次 vector 切片会发生拷贝，实际开销高。
  • 空间复杂度： 较高（频繁分配/复制）。

备注： 此法更直观但不高效，多用于理解或稿子中的思路演示。

方法三：迭代二分切分法（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        // 保证 nums2 是较短的数组（在较短数组上二分）
        if (m < n) return findMedianSortedArrays(nums2, nums1);
        if (n == 0) {
            // nums2 为空，直接返回 nums1 的中位数
            return ((double)nums1[(m - 1) / 2] + (double)nums1[m / 2]) / 2.0;
        }

        int left = 0, right = n * 2; // 使用“插入#后的坐标系”，长度乘2处理奇偶统一
        while (left <= right) {
            int mid2 = (left + right) / 2;     // 在短数组 nums2 上的切分点（*2 坐标系）
            int mid1 = m + n - mid2;          // 在 nums1 上的切分点（由总长度决定）

            double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1 - 1) / 2];
            double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2 - 1) / 2];
            double R1 = (mid1 == m * 2) ? INT_MAX : nums1[mid1 / 2];
            double R2 = (mid2 == n * 2) ? INT_MAX : nums2[mid2 / 2];

            if (L1 > R2) left = mid2 + 1;    // nums1 左边太大，需要把 nums2 的切分点右移（增大 mid2）
            else if (L2 > R1) right = mid2 - 1; // nums2 左边太大，需要把 nums2 的切分点左移
            else {
                // 找到合适切分
                return (max(L1, L2) + min(R1, R2)) / 2.0;
            }
        }
        return -1; // 不应到达
    }
};
  • 时间复杂度： O(log(min(m, n))) —— 在较短的数组上二分。
  • 空间复杂度： O(1)。

关键点：

  • 把两个数组各自切分为左右两部分，保证左边元素总数等于右边元素总数（或相差 1），并且满足 L1 <= R2 && L2 <= R1。
  • 处理边界时把不存在的位置用 INT_MIN / INT_MAX 填充，代码更简洁。
  • 为了使二分在短数组上进行，先交换数组确保 nums2 是较短的。

复杂度与实现要点总结

  • 二分第 K 小（方法一）与迭代切分（方法三）都能满足题目 O(log(m+n)) 的要求，方法三在常见实现中更为优雅且常被面试官接受（时间复杂度 O(log(min(m,n)))）。
  • 注意处理边界（数组为空、切分到末端等）时使用极值占位可以简化判断。
  • 拷贝子数组的方法（方法二）思想清晰但会带来额外拷贝成本，不推荐在面试或性能敏感场景使用。

作者想说的话：
这道题的要点不在于繁琐的实现，而在于能把“中位数”问题转化为「第 k 小」或「两个数组的切分点」问题，然后用二分把问题规模迅速缩小。掌握这些思路后，面对其他需要在两个有序结构上做对齐或分割的问题也会胸有成竹。推荐练习变体题目并手写几次边界情况以加深理解。