Intuitional and fast,python code,250~270ms


  • 0
    L

    2078 / 2078 test cases passed.
    Status: Accepted
    Runtime: 252 ms

    class Solution:
    # @return a float
    def findMedianSortedArrays(self, A, B):
        len_A = len(A);
        len_B = len(B);
        m=0;
        n=0;
        len_sum = len_A+len_B;
        sign    = len_sum%2;
        len_sum = len_sum/2;
        if len_A==0:
            value = B[0];
        elif len_B==0:
            value = A[0];
        else:
            value   = A[0] if A[0]<B[0] else B[0];
    
        while(m+n<=len_sum):
            value1 = value;
            if m>=len_A:
                value = B[n];
                n=n+1;
            elif n>=len_B:
                value = A[m];
                m=m+1;
            elif A[m]<B[n]:
                value = A[m];
                m=m+1;
            else:
                value = B[n];
                n=n+1;
        if not sign:
            return (value+value1)/2.0;
        else:
            return value;

  • 0
    R

    This is O(m+n), not O(log(m+n)). That said, it is still a fast enough solution when better algorithm is not (yet) found. It is really intuitive and runs as fast as the other fast solutions here, at least for OJ samples.


Log in to reply
 

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