4 Median of Two Sorted Arrays 寻找两个有序数组的中位数

Description:
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)).

You may assume nums1 and nums2 cannot be both empty.

Example:

Example 1:

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

The median is 2.0

Example 2:

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

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

题目描述:
给定两个大小为 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(两个数组元素和为奇数)或者2(两个数组元素和为偶数)数组元素, 返回结果的平均值即可
时间复杂度O(log(m + n)), 空间复杂度O(1)

代码:
C++:

class Solution 
{
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
    {
        if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
        int m = nums1.size(), n = nums2.size(), left = 0, right = nums1.size();
        while (left <= right) 
        {
            int i = (left + right) >> 1;
            int j = ((m + n + 1) >> 1) - i;
            int left_max1 = i == 0 ? INT_MIN : nums1[i - 1], right_min1 = i == m ? INT_MAX : nums1[i], left_max2 = j == 0 ? INT_MIN : nums2[j - 1], right_min2 = j == n ? INT_MAX : nums2[j];
            if (left_max1 <= right_min2 and left_max2 <= right_min1) 
            {
                if ((m + n) & 1) return max(left_max1, left_max2);
                else return ((max(left_max1, left_max2) + min(right_min1, right_min2))) / 2.0;
            } 
            else if (left_max2 > right_min1) left = i + 1;
            else right = i - 1;
        }
        return 0.0;
    }
};

Java:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int left = (m + n + 1) >>> 1, right = (m + n + 2) >>> 1;
        return (helper(nums1, 0, nums2, 0, left) + helper(nums1, 0, nums2, 0, right)) / 2.0;
    }
    
    private int helper(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i + 1 > nums1.length) return nums2[j + k - 1];
        if (j + 1 > nums2.length) return nums1[i + k - 1];
        if (k == 1) return Math.min(nums1[i], nums2[j]);
        int mid1 = (i + (k >>> 1) - 1 < nums1.length) ? nums1[i + (k >>> 1) - 1] : Integer.MAX_VALUE, mid2 = (j + (k >>> 1) - 1 < nums2.length) ? nums2[j + (k >>> 1) - 1] : Integer.MAX_VALUE;
        if (mid1 < mid2) return helper(nums1, i + (k >>> 1), nums2, j, k - (k >>> 1));
        else return helper(nums1, i, nums2, j + (k >>> 1), k - (k >>> 1));
    }
}

Python:

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        return 1.0 * sorted(nums1 + nums2)[(len(nums1) + len(nums2)) >> 1] if (len(nums1) + len(nums2)) & 1 else (sorted(nums1 + nums2)[(len(nums1) + len(nums2)) >> 1] + sorted(nums1 + nums2)[((len(nums1) + len(nums2)) >> 1) - 1]) / 2