Concise JAVA solution based on Binary Search


  • 112

    Explanation

    The key point of this problem is to ignore half part of A and B each step recursively by comparing the median of remaining A and B:

    if (aMid < bMid) Keep [aRight + bLeft]    
    else Keep [bRight + aLeft]
    

    As the following: time=O(log(m + n))

    public double findMedianSortedArrays(int[] A, int[] B) {
    	    int m = A.length, n = B.length;
    	    int l = (m + n + 1) / 2;
    	    int r = (m + n + 2) / 2;
    	    return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
    	}
    
    public double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
    	if (aStart > A.length - 1) return B[bStart + k - 1];            
    	if (bStart > B.length - 1) return A[aStart + k - 1];                
    	if (k == 1) return Math.min(A[aStart], B[bStart]);
    	
    	int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
    	if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; 
    	if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1];        
    	
    	if (aMid < bMid) 
    	    return getkth(A, aStart + k/2, B, bStart,       k - k/2);// Check: aRight + bLeft 
    	else 
    	    return getkth(A, aStart,       B, bStart + k/2, k - k/2);// Check: bRight + aLeft
    }

  • 0
    K
    This post is deleted!

  • 0
    H
    This post is deleted!

  • 0
    J

    why do you take the min when k==1?
    "if (k == 1) return Math.min(A[aStart], B[bStart]);"


  • 0
    D

    It means if you want to find the first(k==1) smallest element in two sorted arrays, you should just return the smaller one from the the first elements of the two arrays(Math.min(A[aStart], B[bStart])).


  • 0
    J
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 10
    C

    if (aMid < bMid) Keep [aRight + bLeft]

    else Keep [bRight + aLeft]

    From you code, your logic should be as follows,

    if (aMid < bMid) Keep [aRight + b]

    else Keep [bRight + a]

    Every iteration will get rid of k/2 elements.


  • 0
    J

    Variable k is an implicitly limit of the array length. In each iteration, we find the kth element, so the maximum size of an array is limited to k.


  • 1
    J

    This solution is simple, small and beautiful!


  • 0
    I

    I am puzzled.Why it is O(log(m + n)). It cuts only one per time.How about log(m)+log(n)?


  • 0
    Z

    You are right,but I think each time remove the k/2 elements,not find the kth element exactly.When k =1 is the boundary condition.


  • 0
    J

    the element 'k/2' has some relation with the time limit listed in the question?


  • 2
    G

    each time we remove k/2 until k =1. Since k = (m+n+1)/2. I belive the time is O(log(m+n)).


  • 2
    J

    Hello,
    Your solution is very elegant. I have two questions.

    if (aStart > A.length - 1) return B[bStart + k - 1];            
    if (bStart > B.length - 1) return A[aStart + k - 1];                
    
    if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1]; 
    if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1]; 
    

    in the two set of if statements what and why are you exactly checking?
    Can you give a sample input in which the conditions in the if statements are violated?


  • 0
    D

    What a beautiful solution! Much better then mine.


  • 0
    C
    This post is deleted!

  • 0
    J

    If you combine two arrays, l and r would be their median elements.


  • 0
    T

    your code is elegant,but if m==0&&n==0,the code will be error


Log in to reply
 

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