Description

LeetCode 4

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

 

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Analysis

The idea is not very hard to come up with. But it is too trivial to implement easily because of many corner cases. So we should consider completely before coding.

If we want to find the median of an array, we should partition the array into two parts. The length of two parts are same. And the elements in the left part should be less or equal than the elements in the right part.

In this problem, assuming that the length of \(nums1\) is less than \(nums2\), we should merge \(nums1\) and \(nums2\) to one array that satisfies the former condition. Because \(nums1\) and \(nums2\) are sorted, the left part of the final array should be inserted from the left parts of \(nums1\) and \(nums2\). The right part of the final array should be inserted from the right parts of \(nums1\) and \(nums2\).

If we define \(i\) and \(j\) as the number of elements in the final array’s left part that inserted from \(nums1\) and \(nums2\), then \(j\) depends on \(i\). Because we must ensure that the left part and right part have same length. Define \(n\) and \(m\) as the length of nums1 and nums2. In this analysis, if \(n+m\) is even, the left part is the left helve. But if \(n+m\) is odd, we let the left part includes the middle part. Then \(j=(n+m+1)/2-i\).

Based on the definitions of \(i\) and \(j\), if the index begins from \(0\), then the border elements in \(nums1\) and \(nums2\) are \(nums1[i-1]\), \(nums1[i]\), \(nums2[j-1]\), \(nums2[j]\).

General Condition: odd length and \(0<i<n\) and \(0<j<m\)

If \(nums1[i-1]<=nums2[j]\&\&nums2[j-1]<=nums1[i]\), this condition satisfies that the elements of the left part of the final array are less or equal than the right part. We can temporarily return the median as the maximum of \(nums1[i-1]\) and \(nums2[j-1]\), which is the final result if \(n+m\) is odd.

If \(nums2[j-1]>nums1[i]\), then move \(i\) to right in order to make nums1[i] larger and nums2[j-1] smaller.

If \(nums1[i-1]>nums2[j]\) then move \(i\) to left in order to make nums1[i-1] smaller and nums2[j] larger.

Corner Condition 1: \(i=0\) or\(j=0\) affects the temporary median

In the process, if \(i\) moved to \(0\), it means that all the elements in \(nums1\) are larger than \(nums2\). And now \(j=(n+m+1)/2\), which becomes the ideal result. So just return the temporary median as \(nums2[j-1]\). Similarly, if \(j\) moved to \(0\), it means that all the elements in \(nums2\) are larger than \(nums1\). And now \(i=(n+m+1)/2\), which becomes the ideal result. So just return the temporary median as \(nums1[i-1]\).

Corner Condition 2: \(i=n\) or \(j=m\) affects the next element

On the other hand, when \(i\) moves to \(n\), it means that all the elements in \(nums1\) are smaller than \(nums2\). When \(j\) moves to\(m\), it means that all the elements in \(nums2\) are smaller than \(nums1\). The temporary median can also be returned the correct result with the general condition, that is to say, it can be merged to the general condition. However, the next element of \(nums1[i-1]\) and \(num2[j-1]\) are different with the general condition. If \(i\) moves to \(n\), the next element is \(nums2[j]\). If \(j\) moves to \(m\), the next element is \(nums1[i]\).

Corner Condition 3: even length affects the final median

Now, if \(n+m\) is odd, the temporary median is the final median. However, if \(n+m\) is even, we should return the average of the temporary median and the minimum of \(nums1[i]\) and \(nums2[j]\). If \(i\) moves to \(n\) or \(j\) moves to \(m\), we should return the average the temporary median and the next element discussed before.

Solution

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length>nums2.length) return findMedianSortedArrays(nums2,nums1);
        double median=0;
        if(nums1==null||nums1.length==0)
        {
            median=nums2[(nums2.length-1)/2];
            if(nums2.length%2==1) return median;
            else return (median+nums2[(nums2.length-1)/2+1])/2;
        }
        if(nums2==null||nums2.length==0)
        {
            return 0;
        }
        int low=0,high=nums1.length,i=0,j=0;
        while(low<=high)
        {
            i=(low+high)/2;
            j=(nums1.length+nums2.length+1)/2-i;
            if(i<nums1.length&&j>0&&nums2[j-1]>nums1[i]) low=i+1;
            else if(j<nums2.length&&i>0&&nums1[i-1]>nums2[j]) high=i-1;
            else
            {
                if(i==0) median=nums2[j-1];
                else if(j==0) median=nums1[i-1];
                else median=Math.max(nums1[i-1],nums2[j-1]);
                break;
            }
        }
        if((nums1.length+nums2.length)%2==1) return median;
        if(i==nums1.length) return (median+nums2[j])/2;
        if(j==nums2.length) return (median+nums1[i])/2;
        return (median+Math.min(nums1[i],nums2[j]))/2;  
    }
}

Reference

[1] https://www.geeksforgeeks.org/median-two-sorted-arrays-different-sizes-ologminn-m/

Leave a Reply

Your email address will not be published. Required fields are marked *