20+ python codes in O(log(mn)) with detail analysis


  • 2
    G

    It is the 4th problem I wrote in leetcode, and it took me a long time to figure out the solution.

    I wrote it in 20+ lines python and detail analysis and code are provided on github, very easy to understand.

    I bet you will love my solution ;))

    class Solution(object):
        def findMedianSortedArrays(self, nums1, nums2):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :rtype: float
            """
            def _search(l1, l2, k):
                if len(l1) == 0:
                    return l2[k]
                if len(l2) == 0:
                    return l1[k]
                if k == 0:
                    return min(l1[0], l2[0])
                mid1 = len(l1) >> 1
                mid2 = len(l2) >> 1
                if mid1 + mid2 < k:
                    if l1[mid1] > l2[mid2]:
                        return _search(l1, l2[mid2+1:], k - mid2 - 1)
                    else:
                        return _search(l1[mid1+1:], l2, k - mid1 - 1)
                else:
                    if l1[mid1] > l2[mid2]:
                        return _search(l1[:mid1], l2, k)
                    else:
                        return _search(l1, l2[:mid2], k)
            totalLen = len(nums1) + len(nums2)
            if totalLen % 2 == 0:
                return (_search(nums1, nums2, totalLen >> 1) + _search(nums1, nums2, (totalLen >> 1) - 1)) / 2.0
            else:
                return _search(nums1, nums2, totalLen >> 1)
    

    And I wrote a markdown file on github, which explains the algorithm in great details:

    my analysis


Log in to reply
 

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