Share my O(log(min(m,n)) solution with explanation


  • -1
    P

    Thanks, I found something from your reference:
    '''public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    double median1 = 0;
    double median2 = 0;
    double median = 0;
    Arrays.sort(array1);
    Arrays.sort(array2);
    if (array1.length % 2 == 0) {
    median1 = ((double) array1[array1.length / 2] + (double) array1[array1.length / 2 - 1]) / 2;
    } else {
    median1 = (double) array1[array1.length / 2];
    }
    if (array2.length % 2 == 0) {
    median2 = ((double) array2[array2.length / 2] + (double) array2[array2.length / 2 - 1]) / 2;
    } else {
    median2 = (double) array2[array2.length / 2];
    }
    median = (median1 + median2) / 2;
    return median;
    }
    }'''


  • 0
    K

    class Solution {

    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A; A = B; B = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j-1] > A[i]){
                iMin = iMin + 1; // i is too small
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = iMax - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }
                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }
    
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
    

    }

    two questions in the answer (the first recommended answer):
    1,why the condition is :

    i < iMax && B[j-1] > A[i],
    i > iMin && A[i-1] > B[j])

    why i<iMax and i>iMin

    2,why:

    iMin = iMin + 1; // i is too small ????
    iMax = iMax - 1; // i is too big ????
    why not iMin=i+1? and iMax=i-1?


  • 0
    K

  • 0

    THX for sharing your brilliant idea, rewrite in C++.

    class Solution {
    public:
        double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
            int m = nums1.size(), n = nums2.size();
            if(m > n) return findMedianSortedArrays(nums2, nums1);
            int lo = 0, hi = m, mid = (m + n + 1)/2;
            while(lo <= hi){
                int i = (lo + hi)/2;
                int j = mid - i;
                if(i < m && nums2[j - 1] > nums1[i]) 
                    lo = i + 1;
                else if(i > 0  && nums1[i - 1] > nums2[j])
                    hi = i - 1;
                else{
                    int maxLeft = (i == 0) ? nums2[j - 1] : (j == 0) ? nums1[i - 1] : max(nums1[i - 1], nums2[j - 1]); 
                    int minRight = (i == m) ? nums2[j] : (j == n) ? nums1[i] : min(nums1[i], nums2[j]);
                    return (m + n) % 2 ? maxLeft : (maxLeft + minRight) / 2.0;
                }
            }
        }
    };
    

  • 0
    A

    JAVA Solution

    public double findMedianSortedArrays(int[] A, int[] B){
        int m = A.length;
        int n = B.length;
        if(m > n){
            return findMedianSortedArrays(B, A);
        }
        int minIndex = 0, maxIndex = m, halfLen = (m + n + 1) / 2;
        int maxLeft, minRight;
        while(minIndex <= maxIndex){
            int i = (minIndex + maxIndex) / 2;
            int j = halfLen - i;
            if(i < m && B[j - 1] > A[i]){
                minIndex = i + 1;
            } else if(i > 0 && A[i - 1] > B[j]){
                maxIndex = i - 1;
            } else{
                if(i == 0){
                    maxLeft = B[j - 1];
                } else if(j == 0){
                    maxLeft = A[i - 1];
                } else{
                    maxLeft = Math.max(A[i - 1], B[j - 1]);
                }
                if((m + n) % 2 == 1){
                    return maxLeft;
                }
                if(i == m){
                    minRight = B[j];
                } else if(j == n){
                    minRight = A[i];
                } else{
                    minRight = Math.min(A[i], B[j]);
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0;
    }
    

  • -1
    M
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int[] buf = new int[len1 + len2];
        int i = 0, j = 0, k = 0;
        double median = 0;
        while (i < len1 && j < len2) {
            if (nums1[i] < nums2[j]) {
                buf[k++] = nums1[i++];
            } else {
                buf[k++] = nums2[j++];
            }
        }
        while(i < len1){
            buf[k++] = nums1[i++];
        }
        while(j < len2){
            buf[k++] = nums2[j++];
        }
        int len = buf.length;
        if(len % 2 == 0){
            median = (buf[len / 2] + buf[len / 2 - 1]) / 2.0;
        }else{
            median = buf[len / 2];
        }
        return median;
    }
    

    I think it is easy to understand !


  • 0
    K

    @jialic You'd better review binary search and time complexity part of textbook first before you go through this solution. Six upvotes of your post mean you mislead at least six people about how this solution works.


  • 0
    L

    @jialic It's wrong. Don't mislead others. Since i depends on imin and imax. It seems we do the binary search on the small array. The complexity should be O(log(min(m, n)))


  • 0
    S

    i wonder why (m+n+1)/2 is used instead of (m+n)/2


  • 0
    B
            int len1 = nums1.length;
            int len2 = nums2.length;
            int len = len1 + len2;
            int med = len/2+1;
            //System.out.println(med);
            ArrayList<Integer> list = new ArrayList<>();
            int i=0, j=0;
            while(i+j < med){
                if (i<len1 && j<len2)
                {
                    if (nums1[i] < nums2[j])
                    {
                        list.add(nums1[i]);
                        i++;
                    } else
                    {
                        list.add(nums2[j]);
                        j++;
                    }
                }
                else if (i == len1){
                    for (int k=j; k<len2; k++)
                        list.add(nums2[k]);
                    break;
                }
                else if (j == len2){
                    for (int k=i; k<len1; k++)
                        list.add(nums1[k]);
                    break;
                }
            }
            //for(int k : list)
                //System.out.println(k);
            if ((len&1) != 0)
                return list.get(med-1);
            else
                return (list.get(med-2)+list.get(med-1))/2.0;
        }
    

  • 0
    K

    Clear concise explanation. Thank you.


  • 0
    P

    @MissMary
    Hi,

    Could you explain why, i + j = m - i + n - j + 1 ?
    or rather why do we do a "+1" in this equation.?


  • 0
    N

    @MissMary but in java code, iMin = iMin + 1 ; this is not binary search.


  • 0
    D

    The judging seems to have a problem on this one. The following is the straightforward brute force O(n+m) solution, but it passed and not only that, was faster than 91.78% of swift submissions!

    class Solution {
        func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
            
            let nums = mergeSortedArrs(nums1, nums2)
            //printArr(nums)
            //print("nums1[\(i1)]=\(nums1[i1]) nums2[\(i2)]=\(nums2[i2])")
    
            let N = nums.count
            let medianIndex = N / 2
            
            if N % 2 == 1 { // odd case
                return Double(nums[medianIndex])
            } else { // even case
                return Double(nums[medianIndex-1] + nums[medianIndex])/2
            }
            
        }
        
        func printArr(_ nums: [Int]) -> Void {
            
            print("nums = [", terminator: "")
            for i in 0..<nums.count {
                if (i == nums.count - 1) {
                    print("\(i): \(nums[i])", terminator: "")
                } else {
                    print("\(i): \(nums[i]), ", terminator: "")
                }
            }
            print("]")
        }
        
        private func mergeSortedArrs(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
            var nums = [Int]()
            var i1 = 0
            var i2 = 0
            let N1 = nums1.count
            let N2 = nums2.count
            let N = N1 + N2
            while (i1+i2 < N) {
                if (i1 >= N1) {
                    nums.append(nums2[i2])
                    i2 += 1
                } else if (i2 >= N2) {
                    nums.append(nums1[i1])
                    i1 += 1
                } else {
                    if (nums1[i1] <= nums2[i2]) {
                        nums.append(nums1[i1])
                        i1 += 1
                    } else {
                        nums.append(nums2[i2])
                        i2 += 1
                    }
                }
            }
            
            return nums
        }
    }
    

  • 0
    P

    Great!How do you think of it?How do you think of QSort?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.