4. Median of Two Sorted Arrays

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.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

Solution:

Binary Search:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;

        if (len1 > len2){
            return findMedianSortedArrays(nums2, nums1);
        }

        int left = 0;
        int right = len1;

        // value for the left right boundary of nums

        int l1 = 0;
        int r1 = 0;
        int l2 = 0;
        int r2 = 0;

        while(left <= right){
            int mid1 = left + (right - left)/2;
            int mid2 = (len + 1)/ 2 - mid1; // 6 - 2 = 4
                        // 加 1 是为了处理当元素总数为奇数的情况，使得左半部分比右半部分多一个元素。无论总数是奇数还是偶数，这个分割线都能正确分割数组
            // (m + n + 1) / 2 - i; 
            // 5 + 8 + 1 /2 -3 
            // 13+1 = 14 /2 = 7 - 3 = 4 
            if (mid1 == 0){
                l1 = Integer.MIN_VALUE;
            }else {
                l1 = nums1[mid1 -1];
            }

            if (mid1 == len1){
                r1 = Integer.MAX_VALUE;
            }else {
                r1 = nums1[mid1];
            }

            if (mid2 == 0){
                l2 = Integer.MIN_VALUE;
            }else{
                l2 = nums2[mid2 - 1];
            }

            if (mid2 == len2){
                r2 = Integer.MAX_VALUE;
            }else{
                r2 = nums2[mid2];
            }



            // check 是否满足正确的分割条件
            if (l1 <= r2 && l2 <= r1){
                if ((len) % 2 == 0){
                    return ((double) Math.max(l1, l2) + Math.min(r1, r2)) /2.0;
                }else{
                    return Math.max(l1, l2);
                }
            }else if (l1 > l2){
                right = mid1 - 1;
            }else{
                left = mid1 + 1;
            }


        }

        return -1;


    }
}
// TC: O(log(min(m,n)))
// SC: O(1)

嗯...两天啥也没干是吧...

Two Pointers:

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] nums = new int[nums1.length + nums2.length];

        int i = 0;
        int j = 0;
        int k = 0;

        while (i < nums1.length && j < nums2.length){
            if (nums1[i] < nums2[j]){
                nums[k] = nums1[i];
                k++;
                i++;
            }else {
                nums[k] = nums2[j];
                k++;
                j++;
            }
        }

        while(i < nums1.length){
            nums[k] = nums1[i];
            k++;
            i++;
        }

        while(j < nums2.length){
            nums[k] = nums2[j];
            k++;
            j++;
        }

        int mid = nums.length / 2;
        if (nums.length % 2 == 0){
            return (nums[mid - 1] + nums[mid] )/2.0;
        }else{
            return nums[mid];
        }

    }
}


// TC: O(n + m)
// SC: O(n + m)

虽然能过 但其实是不满足题意的

https://www.youtube.com/watch?v=q6IEA26hvXc

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int half = (nums1.length +nums2.length)/2;

        if(nums2.length <nums1.length){
            return findMedianSortedArrays(nums2,nums1);
        }

        int left = 0;
        int right = nums1.length-1;
        while(true){
            int mid1 =(int)Math.floor((right+left)/2.0);
            int mid2 = half -(mid1+1)-1;
            int l1 = mid1>=0?nums1[mid1]:Integer.MIN_VALUE;
            int l2 = mid2>=0?nums2[mid2]:Integer.MIN_VALUE;
            int r1 = (mid1+1)<nums1.length?nums1[mid1+1]:Integer.MAX_VALUE;
            int r2 = (mid2+1)<nums2.length?nums2[mid2+1]:Integer.MAX_VALUE;
            if(l1<=r2 && l2<=r1 ){
                //found it
                if((nums1.length+nums2.length) %2 ==0){
                    return ((double)Math.max(l1,l2) +(double)Math.min(r1,r2))/2.0;
                }else{
                    return Math.min(r1,r2);
                }
            }
            else if(l1>r2){
                right = mid1-1;
            }else{
                left = mid1+1;
            }
        }

    }
}