9 lines O(log(min(m,n))) Python


  • 3

    Same method as my 6-lines Ruby solution, just the binary search and the "get up to two" isn't quite as convenient in Python. See there if you'd like an explanation.


    Solution 1

    This one is a bit of a hack, as bisect_left is intended for lists, but apparently it's happy enough with something that behaves enough like a list (supports __getitem__):

    def findMedianSortedArrays(self, nums1, nums2):
        a, b = sorted((nums1, nums2), key=len)
        m, n = len(a), len(b)
        after = (m + n - 1) / 2
        class Range:
            def __getitem__(self, i):
                return after-i-1 < 0 or a[i] >= b[after-i-1]
        i = bisect.bisect_left(Range(), True, 0, m)
        nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
        return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2.0
    

    Solution 2

    Same, just with a self-made binary search:

    def findMedianSortedArrays(self, nums1, nums2):
        a, b = sorted((nums1, nums2), key=len)
        m, n = len(a), len(b)
        after = (m + n - 1) / 2
        lo, hi = 0, m
        while lo < hi:
            i = (lo + hi) / 2
            if after-i-1 < 0 or a[i] >= b[after-i-1]:
                hi = i
            else:
                lo = i + 1
        i = lo
        nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
        return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2.0

  • 1
    Z

    Here's my code based on your Solution 2, with some comments.

    def findMedianSortedArrays(self, nums1, nums2):
        a, b = sorted((nums1, nums2), key=len)
        m, n = len(a), len(b)
        after = (m + n - 1) / 2
        # Determine i, j that a[0:i] + b[0:j] (exclusive) is the most small "after" numbers.
        # There could multiple pairs of such (i, j) if there are some duplicated numbers.
        # Each each such pair satisfies the following criteria at the same time:
        # 1) i + j == after
        # 2) (j>=1 and a[i] >= b[j-1]) or j==0
        # 3) (i>=1 and b[j] >= a[i-1]) or i==0
        lo, hi = 0, m
        while lo < hi:
            i = (lo + hi) / 2
            j = after - i
            cond1 = (j>=1 and a[i] >= b[j-1]) or j==0
            cond2 = (i>=1 and b[j] >= a[i-1]) or i==0
            if(cond1 and cond2):
                lo = i
                break
            elif(not cond1):
                assert(cond2)
                lo = i + 1
            else:
                assert(cond1)
                hi = i
        i = lo
        j = after - i
        nextfew = sorted(a[i:i+2] + b[j:j+2])
        return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2.0
    

Log in to reply
 

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