【算法LeetCode】第四题 - 寻找两个正序数组的中位数（困难）

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length+nums2.length;
        int[] list = new int[len];
        int m = 0, i=0, j=0;
        while(i<nums1.length && j<nums2.length) {
            if(nums1[i]<nums2[j]){
                list[m++] = nums1[i++];
            } else {
                list[m++] = nums2[j++];
            }
        }
        if(i != nums1.length){
            for( ; i<nums1.length; i++){
                list[m++] = nums1[i];
            }
        } else {
            for( ; j<nums2.length;j++){
                list[m++] = nums2[j];
            }
        }
        
        double count=0;
        if(len%2!=0){
            count = list[len/2];
            return count;
        } else {
            count =  ((double)list[len/2]+(double)list[len/2-1])/2;
            return count;
        }
    }
}

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;
        int left = 0, right = m;
        // median1：前一部分的最大值
        // median2：后一部分的最小值
        int median1 = 0, median2 = 0;


        while (left <= right) {
            // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
            // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
            int i = (left + right) / 2;
            int j = (m + n + 1) / 2 - i;


            // nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]
            int nums_im1 = (i == 0 ? Integer.MIN_VALUE : nums1[i - 1]);
            int nums_i = (i == m ? Integer.MAX_VALUE : nums1[i]);
            int nums_jm1 = (j == 0 ? Integer.MIN_VALUE : nums2[j - 1]);
            int nums_j = (j == n ? Integer.MAX_VALUE : nums2[j]);


            if (nums_im1 <= nums_j) {
                median1 = Math.max(nums_im1, nums_jm1);
                median2 = Math.min(nums_i, nums_j);
                left = i + 1;
            } else {
                right = i - 1;
            }
        }


        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
}


// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。