4. Median of Two Sorted Arrays

问题

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

输入

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

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

输出

• The median is 2.0

• The median is (2 + 3)/2 = 2.5

分析

要注意题目中的数组已经排序好了。排序数组，复杂度又要求是O(log(m+n))，很容易联想到二分搜索。

举个例子，有两个排序数组，分别为：
A：1 3 5
B：2 4 6 8
显然，中位数应该是两个数组所有元素从小到大排序后的第4个数。
首先，我们比较两个数组的第4/2=2个数，A的第2个数为3，B的第2个数为4，A[2] < B[2]（为了方便起见，索引从1开始）。我们可以确定中位数不会在A[1]-A[2]范围中，这样就把搜索范围缩小了4/2个。

扩展到一般情况，每次比较A[k/2]和B[k/2]之后，都可以把A或者B的搜素范围缩小一半，即不断地二分，计算复杂度为O(log(m+n))。

要点

二分搜索 递归

时间复杂度

O(log(m+n))

空间复杂度

O(log(m+n))，递归需要栈空间

代码

class Solution {
public:
    int findKthNum(const vector<int> &a, int begA, const vector<int> &b, int begB, int k)
    {
        if (a.size() - begA > b.size() - begB) // 始终保持a的长度小于b，避免以后不必要的分情况讨论
            return findKthNum(b, begB, a, begA, k);
        if (a.size() - begA == 0) // 如果a的搜索空间为空，直接返回b的第k个数
            return b[begB + k - 1];
        if (k == 1) // 如果k为1，直接返回a和b的搜索空间的第一个值的最小值
            return min(a[begA], b[begB]);
    
        int pa = min(k / 2, (int)(a.size()) - begA); // 避免pa大于a的搜索空间的大小
        int pb = k - pa;
        
        if (a[begA + pa - 1] == b[begB + pb - 1]) // 如果相等，说明已经找到了中位数
            return a[begA + pa - 1];
        else if (a[begA + pa - 1] < b[begB + pb - 1]) 
            return findKthNum(a, begA + pa, b, begB, k - pa); // 二分a
        else 
            return findKthNum(a, begA, b, begB + pb, k - pb); // 二分b
    }
    
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size() + nums2.size();

        // 对n的奇偶性分情况讨论
        if (n & 0x1)
        {
            return findKthNum(nums1, 0, nums2, 0, n / 2 + 1);
        }
        else
        {
            return (findKthNum(nums1, 0, nums2, 0, n / 2) + findKthNum(nums1, 0, nums2, 0, n / 2 + 1)) / 2.0;
        }
    }
};