题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

样例1

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

则中位数是 2.0

样例2

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

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

算法1

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

中位数的定义为第 $k = \lfloor\frac{m + n + 1}{2}\rfloor$ 大的数。我们可以在第一个数组里取前 $\lfloor\frac{k}{2}\rfloor$ 个数，设取到的最后一个数为nums1[x]，在第二个数组里取前 $k - \lfloor\frac{k}{2}\rfloor$ 个数，设取到的最后一个数为nums2[y]。设第 $k$ 大的数是nums[k]，那么会有:

• nums2[y] <= nums[k] <= nums1[x] || nums1[x] <= nums[k] <= nums2[y]

假如nums1[x] >= nums2[y]，我们可以得到第二堆数都会小于等于nums[k]。所以我们可以将第二堆数从nums2中去掉然后递归的去找第 $\lfloor\frac{k}{2}\rfloor$ 大的数。同理我们也可以去掉第一堆的数然后递归的去找第 $k - \lfloor\frac{k}{2}\rfloor$ 大的数。

注意这里在取数的时候可能会出现数量不足的情况，比如nums1剩下的数不足 $\lfloor\frac{k}{2}\rfloor$ 个，那么我们就将它们全部取出来，递归时减去的数目应该是剩下数的个数而不是 $\lfloor\frac{k}{2}\rfloor$。

递归结束的边界条件是只剩下一个数组时或者当 $k = 1$ 的时候。

时间复杂度

每次递归都会将 $k$ 的规模减小一半，而 $k = \lfloor\frac{m + n + 1}{2}\rfloor$，所以时间复杂度为 $O(\log(m + n))$。

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        if (n + m & 1) {
            return find(nums1, 0, nums2, 0, (n + m + 1) >> 1);
        }

        int left = find(nums1, 0, nums2, 0, n + m >> 1);
        int right = find(nums1, 0, nums2, 0, (n + m >> 1) + 1);
        return (left + right) / 2.0;
    }

    int find(vector<int> &nums1, int l1, vector<int> &nums2, int l2, int k) {
        if (l1 >= nums1.size()) return nums2[l2 + k - 1];
        if (l2 >= nums2.size()) return nums1[l1 + k - 1];
        if (k == 1) {
            if (nums1[l1] < nums2[l2]) return nums1[l1];
            return nums2[l2];
        }

        int idx1 = l1 + (k / 2) - 1, idx2 = l2 + (k - k / 2) - 1;
        if (idx1 >= nums1.size()) idx1 = nums1.size() - 1;
        if (idx2 >= nums2.size()) idx2 = nums2.size() - 1;

        if (nums1[idx1] >= nums2[idx2]) {
            return find(nums1, l1, nums2, idx2 + 1, k - (idx2 - l2 + 1));
        }
        return find(nums1, idx1 + 1, nums2, l2, k - (idx1 - l1 + 1));
    }
};

算法2

(二分) $O(\log(min(m, n)))$

通过算法一的分析，我们可以发现当数组给定的时候，前 $k$ 个数在两个数组里的分布是唯一的，不妨设答案是在第一个数组里取 $i$ 个数，那么在第二个数组里就应该取 $k - i$ 个数，使得这样选出来的数就是两个数组合并后的前 $k$ 大的数。并且这样会将数组分为两部分，左半部分就是前 $k$ 大的数，右半部分是除去前 $k$ 大数剩余的部分。

下面我们观察在第一个数组取数的数量是否具有二分性：

          left_part          |        right_part
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

假如我们选得数量是正确的的话那么我们会有两个性质： $A[i - 1] <= B[j]$ 并且 $B[j - 1] <= A[i]$。

假如我们有 $A[i - 1] > B[j]$，不满足第一个性质，那么就说明我们在第一个数组里选得太多了。同理假如我们有 $B[j - 1] > A[i]$，不满足第二个性质，那么就说明我们在第一个数组里选得太少了。

可以看出选得数量具有二分性，我们就可以二分出需要在第一个数组里选多少数。

在取数的时候我们会有边界问题，假如我们需要在第一个数组或第二个数组里取0个数，我们可以将该值赋为INT_MIN使得 $A[i - 1] <= B[j]$ 或者 $B[j - 1] <= A[i]$ 恒成立，同理假如我们取得数超过了数组的长度我们就将该值赋为INT_MAX。

时间复杂度

我们总是二分长度较小的那个数组，因此时间复杂度为 $O(\log(min(m, n)))$。

C++ 代码

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

        int l = 0, r = m;
        int k = m + n + 1 >> 1;
        int l1, l2, r1, r2;
        while (l <= r) {
            int mid = l + r >> 1;
            l1 = mid == 0 ? INT_MIN : nums1[mid - 1];
            l2 = k - mid == 0 ? INT_MIN : nums2[k - mid - 1];
            r1 = mid == m ? INT_MAX : nums1[mid];
            r2 = k - mid == n ? INT_MAX : nums2[k - mid];
            if (l1 > r2) r = mid - 1;
            else if (l2 > r1) l = mid + 1;
            else break;
        }
        if (m + n & 1) return max(l1, l2);
        return (max(l1, l2) + min(r1, r2)) / 2.0;
    }
};