4 Median of Two Sorted Arrays

LeetCode

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

---

这道题十分难，边界条件复杂。

使用二分才能使时间复杂度为 o(log n) 。定义一种切分方式，将两个数组切分为 2 段，这 2 段数量相等或者左边多 1 个元素。定义较短数组上坐标 i 左边的元素为第 1 段（如果 i 等于数组长度，则全部为第 1 段，如果 i 为 0 则全部为第 2 段），较长数组上坐标 j 左边的元素为第 1 段， i+j 等于左边元素数量和。

从 0 到短数组长度，二分查找。选短数组是为了时切线在长数组上存在。使用较短数组第 1 段最大的元素和较长数组第 2 段最小的元素比较，如果大于，说明切分线太靠右了，右边界变为中间下标减 1 ，如果小于等于，说明切分线可能是正确的，也可能太小，左边界变为中间下标。求中间元素时 (right+left+1)/2 这里加 1 是为了防止 right=left+1 时陷入死循环，同时它也防止中间元素为 0 导致 nums[i-1] 越界，因此不需要再判断越界。

最后根据切分位置左右两边的元素求出中间元素，由于切分点可能在数组两端，需要注意边界条件。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    
    if(nums1.length>nums2.length){
        int[] t = nums1;
        nums1 = nums2;
        nums2 = t;
    }
    
    int len1 = nums1.length;
    int len2 = nums2.length;

    int totalLeft = (len1+len2+1)/2;
    
    int left = 0;
    int right = len1;
    
    while(left<right){
        int mid = (right+left+1)/2;
        int i = mid;
        int j = totalLeft - i;
        if(nums1[i-1]>nums2[j]){
            right = mid - 1;
        } else {
            left = mid;
        }
    }
    
    int i = left;
    int j = totalLeft - i;
    int leftMax1 = i==0? Integer.MIN_VALUE: nums1[i-1];
    int leftMax2 = j==0? Integer.MIN_VALUE: nums2[j-1];
    int rightMin1 = i==len1? Integer.MAX_VALUE: nums1[i];
    int rightMin2 = j==len2? Integer.MAX_VALUE: nums2[j];
    int leftMax = leftMax1>leftMax2? leftMax1:leftMax2;
    int rightMin = rightMin1<rightMin2? rightMin1:rightMin2;
    if(((len1+len2) & 1)==0){
        return (leftMax+rightMin)/2.0d;
    } else {
        return (double) leftMax;
    }
}