4. 寻找两个正序数组的中位数

题目链接

解析

两个有序数组如何求中位数呢？把两个有序数组排序？将两个有序数组排序的时间复杂度至少为(O(m+n))，不符合时间复杂度(O(log(m+n)))的要求。

本题需用到的两个点：

1. 由(O(log(m+n)))可知需要用二分法，
2. 中位数的性质，小于中位数的数的数量和大于中位数的数的数量一样多。

假如我们在数组1中找到一个切分点mid1，同时由中位数的性质在数组2中确定一个切分点mid2，若两个切分点满足：数组1中mid1左侧的数+数组2中mid2左侧的数均小于数组1中mid1右侧的数+数组2中mid2右侧的数，那么这两个切分点就成功将两个数组划分为两部分，两部分数量相等，且其中一部分的数均小于另一部分，即可从中得到中位数。

复杂度

只需要二分查找较小的数组，所以时间复杂度为(O(min(m,n)))。

实现

C++

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int len1 = nums1.size(), len2 = nums2.size();
        if (0 == len1)  // 处理特殊情况
            return len2 % 2 == 0 ? (double(nums2[len2 / 2 - 1]) + double(nums2[len2 / 2])) / 2 : nums2[len2 / 2];
        if(0 == len2)
            return len1 % 2 == 0 ? (double(nums1[len1 / 2 - 1]) + double(nums1[len1 / 2])) / 2 : nums1[len1 / 2];


        if (len1 > len2)  // 只二分查找较小的数组
            return findMedianSortedArrays(nums2, nums1);
        
        int len = len1 + len2;

        int low = 0, high = len1, k = len >> 1;
        int mid1, mid2, left1, right1, left2, right2;
        while (1) {
            mid1 = low + ((high - low) >> 1);  // 确定切分点mid1
            mid2 = k - mid1;  // 根据中位数性质确定切分点mid2
            left1 = mid1 == 0 ? INT_MIN : nums1[mid1 - 1];  // 需要处理边界点
            right1 = mid1 == len1 ? INT_MAX : nums1[mid1];
            left2 = mid2 == 0 ? INT_MIN : nums2[mid2 - 1];
            right2 = mid2 == len2 ? INT_MAX : nums2[mid2];

            if (left1 > right2) high = mid1 - 1;  // 左移
            else if (left2 > right1) low = mid1 + 1;  // 右移
            else {
                if (len % 2 == 0) return (double(max(left1, left2)) + double(min(right1, right2))) / 2;  // 偶数情况
                else return min(right1, right2);  // 奇数情况
            }
        }
    }
};