My Python solution. The corner cases are frustrating.


  • 0
    P
    class Solution:
    # @param {integer[]} nums1
    # @param {integer[]} nums2
    # @return {float}
    def findMedianSortedArrays(self, nums1, nums2):
        n = len(nums1)
        m = len(nums2)
        even = True if (m + n) % 2 == 0 else False
        def findkth(num1, s1, e1, num2, s2, e2, k):
            if e2 - s2 < e1 - s1:
               num1, num2 = num2, num1
               s1, s2 = s2, s1
               e1, e2 = e2, e1
            if e1 == s1:
                return float(num2[s2 + k - 1])
            if k == 1:
                return float(min(num1[s1], num2[s2]))
            if e1 == s1 + 1:
                if s2 + k - 1 == e2:
                    return max(num2[s2 + k - 2], num1[s1])
                else:
                    return (num2[s2 + k - 2] if num1[s1] <= num2[s2 + k - 2] 
                        else min(num1[s1], num2[s2 + k - 1]))
            l1 = min(e1 - s1, k)
            l2 = min(e2 - s2, k)
            m1 = num1[s1 + l1 / 2 - 1]
            m2 = num2[s2 + l2 / 2 - 1]
            if m1 == m2 and l1/2 + l2/2 == k:
                return m1
            if m1 <= m2:
                return findkth(num1, s1 + l1/2, s1 + l1, num2, s2, s2 + l2, k - l1/2)
            if m1 > m2:
                return findkth(num1, s1, s1 + l1, num2, s2 + l2/2, s2 + l2, k - l2/2)
        k = (m + n + 1) / 2
        if even:
            k1 = findkth(nums1, 0, n, nums2, 0, m, k)
            k2 = findkth(nums1, 0, n, nums2, 0, m, k + 1)
            return (k1 + k2) / 2.0
        else:
            return findkth(nums1, 0, n, nums2, 0, m, k)
    

    Help me make it more concise if you can.


Log in to reply
 

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