Python code for simple logic


  • 0
    L

    I use the logic that tracing the number from start and end at the same time and the median is the number when start-tracing and end-tracing encounters.

        def findMedianSortedArrays(self, nums1, nums2):
            l1, l2 = len(nums1), len(nums2)
            if l1 > l2:
                nums1, nums2, l1, l2 = nums2, nums1, l2, l1
    
            i0, j0 = 0, 0
            it, jt = l1 - 1, l2 - 1
    
            if l1 < 1:
                if l2 < 1:
                    return None
                else:
                    return float(nums2[l2 // 2] + nums2[(l2 - 1) // 2]) / 2
    
            for _ in range((l1 + l2 + 1) // 2):
                if i0 >= l1:
                    a = nums2[j0]
                    j0 += 1
                if j0 >= l2:
                    a = nums1[i0]
                    i0 += 1
                if i0 < l1 and j0 < l2:
                    if nums1[i0] <= nums2[j0]:
                        a = nums1[i0]
                        i0 += 1
                    elif nums1[i0] > nums2[j0]:
                        a = nums2[j0]
                        j0 += 1
                if it < 0:
                    b = nums2[jt]
                    jt -= 1
                if jt < 0:
                    b = nums1[it]
                    it -= 1
                if it >= 0 and jt >= 0:
                    if nums1[it] >= nums2[jt]:
                        b = nums1[it]
                        it -= 1
                    elif nums1[it] < nums2[jt]:
                        b = nums2[jt]
                        jt -= 1
    
            return float(a + b) / 2

  • 0
    D

    At first glance this code runs in O(n+m) time. The judging code will accept it, but it's not quite the O(log(n+m)) solution that the problem asks for.

    You can probably make it twice as fast (but still O(n+m)) by not doing the jt/it iteration, because when you have a list with an even number of items, the two items you average for the median are adjacent to one-another. In other words, if you find i0 and j0, then jt and it are going to be at most one index over.


Log in to reply
 

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