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

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解、时间复杂度O(log(m+n))，用二分法完成，求解nums1和nums2的中分线，设置合并后数组中分线左边个数，当数组元素总数为奇数，左边个数比右边个数多1(n1 + n2 + 1 / 2)，当数组元素个数为偶数，左右相等((n1 + n2) / 2)，因为编程语言中，整数除法向下取整，所以偶数的分子 + 1，无影响，将奇偶两种情况合并。使较长的数组分割线左右两侧均有元素，开始时进行比较，将较长长度的数组放在参数二的位置，到时第二个数组的中分线右侧索引j（第二个数组中分线左侧元素个数） = 左边总元素的个数-第一个数组中分线右侧索引i(第一个数组中分线左侧元素个数)。求第一个数组的中分线位置，找到后相减第二个数组中分线位置get！

第一个数组中分线位置寻找是本题二分法的考察点

①left = 0, right = n1;

②while(left < right){……}，出来时找到中分线，第一个数组中分线右侧的元素索引 i = (left + (right - left + 1) / 2)   奇数个元素数组中点后一个数，偶数个元素数组靠后的中点，同时避免索引为0时的索引越界以及死循环找不到中点。

之后讨论中分线左右两侧不存在元素的情况。

再根据元素总数的奇偶求中位数即可。

class Solution{
    public double findMedianSortedArrays(int[] nums1, int[] nums2){
        int n1 = nums1.length, n2 = nums2.length;
        if(n1 > n2){
            return findMedianSortedArrays(nums2, nums1);
        }
        int totalLeft = n1 + (n2 - n1 + 1) / 2;
        int left = 0;
        int right = n1;
        while(left < right){
            int i = left + (right - left + 1) / 2;
            int j = totalLeft - i;
            if(nums1[i - 1] > nums2[j]){
                right = i - 1;
            }else{
                left = i;
            }
        }
        int i = left;
        int j = totalLeft - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == n1 ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n2 ? Integer.MAX_VALUE : nums2[j];
        if((n1 + n2) % 2 == 1){
            return Math.max(nums1LeftMax, nums2LeftMax);
        }else{
            return (double)(Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin)) / 2;
        }
        
    }
}

详解请见寻找两个有序数组的中位数 - 寻找两个正序数组的中位数 - 力扣（LeetCode）