题目描述

给定两个有序数组 nums1 和 nums2，长度分别为 $m, n$。请找出它们的中位数，要求时间复杂度在 $O(log(n + m))$ 以内。

样例1

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

样例2

nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3) / 2 = 2.5

算法1

(递归) $O(log(n + m))$

原问题难以直接递归求解，所以我们先考虑这样一个问题：

在两个有序数组中，找出第k小数。

如果该问题可以解决，那么第 $(n + m) / 2$ 小数就是我们要求的中位数.

先从简单情况入手，假设 $m, n \geq k/2$，我们先从 $nums1$ 和 $nums2$ 中各取前 $k/2$ 个元素：

• 如果 $nums1[k/2-1] > nums2[k/2-1]$，则说明 $nums1$ 中取的元素过多，$nums2$ 中取的元素过少；因此 $nums2$ 中的前 $k/2$ 个元素一定都小于等于第 $k$ 小数，所以我们可以先取出这些数，将问题归约成在剩下的数中找第 $k - \lfloor k/2 \rfloor$ 小数.
• 如果 $nums1[k/2-1] \leq nums2[k/2-1]$，同理可说明 $nums1$ 中的前 $k/2$ 个元素一定都小于等于第 $k$ 小数，类似可将问题的规模减少一半.

现在考虑边界情况，如果 $m < k/2$，则我们从 $nums1$ 中取m个元素，从$nums2$ 中取 $k/2$ 个元素（由于 $k = (n + m) / 2$，因此 $m,n$ 不可能同时小于 $k/2$.）：

• 如果 $nums1[m-1] > nums2[k/2-1]$，则 $nums2$ 中的前 $k/2$ 个元素一定都小于等于第 $k$ 小数，我们可以将问题归约成在剩下的数中找第 $k - \lfloor k/2 \rfloor$ 小数.
• 如果 $nums1[m-1] \leq nums2[k/2-1]$，则 $nums1$ 中的所有元素一定都小于等于第 $k$ 小数，因此第k小数是 $nums2[k - m - 1]$.

时间复杂度分析：$k = (m + n) / 2$，且每次递归 $k$ 的规模都减少一半，因此时间复杂度是 $O(log(m + n))$.

C++ 代码：

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        if (total % 2 == 0)
        {
            int left = findKthNumber(nums1, 0, nums2, 0, total / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
            return (left + right) / 2.0;
        }
        else
        {
            return findKthNumber(nums1, 0, nums2, 0, total / 2 + 1);
        }
    }

    int findKthNumber(vector<int> &nums1, int i, vector<int> &nums2, int j, int k)
    {
        if (nums1.size() - i > nums2.size() - j) return findKthNumber(nums2, j, nums1, i, k);
        if (nums1.size() == i) return nums2[j + k - 1];
        if (k == 1) return min(nums1[i], nums2[j]);
        int si = min(i + k / 2, int(nums1.size())), sj = j + k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
        {
            return findKthNumber(nums1, i, nums2, j + k / 2, k - k / 2);
        }
        else
        {
            return findKthNumber(nums1, si, nums2, j, k - (si - i));
        }
    }
};

算法2

（二分） $O(log(min(m, n))$

该算法的处理细节非常繁琐，建议新手直接跳过。
首先，让我们考虑只有一个有序数组的情况：

如果我们将有序数组切分为等长的左右两部分，则 中位数 = (左半边的最大值 + 右半边的最小值) / 2.

切分情况有两种，例如：

• 数组长度是偶数，对于 [2 3 5 7], 我们在3和5之间切分：[2 3 / 5 7]，则 中位数 $=(3+5)/2$；
• 数组长度是奇数，对于 [2 3 4 5 7]，我们在4的位置切分，且让4属于左右两边：[2 3 (4/4) 5 7]，则 中位数 $=(4+4)/2$.

现在让我们来考虑两个有序数组的情况，类似于上述考虑方式：

我们在两个数组中分别找到一个分割点（分割点可能在相邻数之间，也可能在数上），两个分割点左边元素的总个数等于右边元素的总个数，且左边元素的最大值 <= 右边元素的最小值，则该分割点即为所求。

为了同时处理分割点在两数之间和在数上的情况，我们在数组中可能是分割点的位置添加虚拟元素 ‘@’，这样我们枚举数组 $A_{1}’$ 的所有元素，即可枚举 $A_{1}$ 所有可能的分割点：

$A_{1}: [1, 2, 3, 4, 5] => A_{1}’: [@, 1, @, 2, @, 3, @, 4, @, 5, @]$
$A_{2}: [1, 1, 1, 1] => A_{2}’: [@, 1, @, 1, @, 1, @, 1, @]$

我们将数组 $A_{1}$ 的长度记为 $N_{1}$，则 $A_{1}’$ 的长度为 $2 * N_{1} + 1$; $A_{2}$ 的长度记为 $N_{2}$，则 $A_{2}’$ 的长度为 $2 * N_{2} + 1$. 总共有 $2N_{1} + 2N_{2} + 2$ 个元素.

假设数组 $A_{1}’$ 的分割点下标是 $C_{1}$，数组 $A_{2}’$ 的分割点下标是 $C_{2}$，则 $C_{1}$ 和 $C_{2}$ 之间具有如下等式关系：
$$ C_{1} + C_{2} = N_{1} + N_{2} $$
证明：除了 $C_{1}$ 和 $C_{2}$ 以外，共有 $2N_{1} + 2N_{2}$ 个元素，要平均分配到左右两边，因此左边共有 $N_{1} + N_{2}$ 个元素. 数组下标从0开始，下标为 $C_{1}$ 的元素左边有 $C_{1}$ 个元素，下标为 $C_{2}$ 的元素左边有 $C_{2}$ 个元素，由此可得上述等式.

为了方便表述，在 $A_{1}’$ 中，$C_{1}$ 左边（包括$C_{1}$）的最大值记为 $L_{1}$，$C_{1}$ 右边（包括$C_{1}$）的最小值记为 $R_{1}$；在 $A_{2}’$ 中，$C_{2}$ 左边（包括$C_{2}$）的最大值记为 $L_{2}$，$C_{2}$ 右边（包括$C_{2}$）的最小值记为 $R_{2}$；

则如果我们选取的分割点满足
$$ L_{1} <= R_{1} \&\& L_{1} <= R_{2} \&\& L_{2} <= R_{1} \&\& L_{2} <= R_{2} $$
则分割点即为所求. 由于 $A_{1}, A_{2}$ 都是有序的，因此 $L_{1} <= R_{1} \&\& L_{2} <= R_{2}$ 一定满足；
不满足的情况有两种：

• 如果 $L_{1} > R_{2}$，表示 $A_{2}$中在分割点左侧的元素太少，此时我们需要将 $C_{2}$ 右移；
• 如果 $L_{2} > R_{1}$，表示 $A_{2}$中在分割点左侧的元素太多，此时我们需要将 $C_{2}$ 左移；

符合二分结构.

另外，我们在实际操作中，不需要真的在原数组中插入 ‘@’，只需找出 $L_{1}, R_{1}, L_{2}, R_{2}$ 和 $C_{1}, C_{2}$ 的关系即可.
我们可以列表找规律：

由此我们可以发现:

• $L_{1} = A_{1}[(C_{1}-1)/2]$
• $R_{1} = A_{1}[C_{1}/2]$

类似可得：

• $L_{2} = A_{2}[(C_{2}-1)/2]$
• $R_{2} = A_{2}[C_{2}/2]$

最后，还有两点需要注意：

1. 我们只能二分长度较小的数组，因为长度较长的数组中的某些分割点可能不合法，会出现 $C_{1} > N_{1} + N_{2}$ 的情况；
2. 我们在数组边界设置两个哨兵，来处理 $C_{1} = 0$ 或 $C_{1} = 2N_{1}$ 的情况：$A_{1}[-1]=INTMIN, A_{1}[2N]=INTMAX$. 这样做并不会影响结果，但可以简化代码.

时间复杂度：二分长度较短的数组，且每次二分的复杂度是 $O(1)$，所以总复杂度是 $O(log(min(n, m)))$.

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int N1 = nums1.size();
        int N2 = nums2.size();
        if (N1 < N2) return findMedianSortedArrays(nums2, nums1);

        int lo = 0, hi = N2 * 2;
        while (lo <= hi) {
            int mid2 = (lo + hi) / 2;
            int mid1 = N1 + N2 - mid2;

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

            if (L1 > R2) lo = mid2 + 1;
            else if (L2 > R1) hi = mid2 - 1;
            else return (max(L1,L2) + min(R1, R2)) / 2;
        }
        return -1;
    }
};