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

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

给定两个大小为 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

先考虑一个有序数组中查找中位数的情况：当数组元素为奇数时，取最中间的一个元素；当数组元素为偶数时，取最中间的两个元素的平均值。

有两个有序数组时我们先计算出总数组的长度，在两个数组中间画一条分割线，当两条分割线左侧的元素个数为总数组长度的一半时，在分割线左右的四个元素则是构成中位数的元素。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length){
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;
        //分割线左边的所有元素需要满足的个数(m + n + 1) / 2
        int totalLeft = (m + n + 1) / 2;
        //在 nums1 的区间 [0, m]里查找恰当的分割线
        //使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
        //在较小长度的数组使用二分查找
        int left = 0;
        int right = m;

        while(left < right){
            //向上取整
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;
            //搜索分割线位置
            if(nums1[i - 1] > nums2[j]){//不满足交叉小于的情况
                //下一轮搜索区间 [left, i - 1]
                right = i - 1;
            }else{
                //下一轮搜索区间 [i, right]
                left = i;
            }
        }

        int i = left;
        int j = totalLeft - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMIn = j == n ? Integer.MAX_VALUE : nums2[j];

        if((m + n) % 2 == 1){
            return Math.max(nums1LeftMax, nums2LeftMax);
        }else{
            return (double)((Math.max(nums1LeftMax,nums2LeftMax) + Math.min(nums1RightMin, nums2RightMIn))) / 2;
        }
    }
}

时间复杂度是 O( log( min(m,n) ) )，空间复杂度：O(1)。