Python O(lg(m+n)) recursive solution.


  • 3
    C
    def findMedianSortedArrays(self, nums1, nums2):
        l = len(nums1) + len(nums2)
        if l % 2:  # the length is odd
            return self.findKthSmallest(nums1, nums2, l//2+1)
        else:
            return (self.findKthSmallest(nums1, nums2, l//2) +
            self.findKthSmallest(nums1, nums2, l//2+1))*0.5
        
    def findKthSmallest(self, nums1, nums2, k):
        # force nums1 is not longer than nums2
        if len(nums1) > len(nums2):
            return self.findKthSmallest(nums2, nums1, k)
        if not nums1:
            return nums2[k-1]
        if k == 1:
            return min(nums1[0], nums2[0])
        pa = min(k/2, len(nums1)); pb = k-pa  # take care here
        if nums1[pa-1] <= nums2[pb-1]:
            return self.findKthSmallest(nums1[pa:], nums2, k-pa)
        else:
            return self.findKthSmallest(nums1, nums2[pb:], k-pb)

  • 3
    Y

    Here is my solution

    class Solution:
    # @return a float
    def findMedianSortedArrays(self, A, B):
        l=len(A)+len(B)
        return self.findKth(A,B,l//2) if l%2==1 else (self.findKth(A,B,l//2-1)+self.findKth(A,B,l//2))/2.0
    
    
    def findKth(self,A,B,k):
        if len(A)>len(B):
            A,B=B,A
        if not A:
            return B[k]
        if k==len(A)+len(B)-1:
            return max(A[-1],B[-1])
        i=len(A)//2
        j=k-i
        if A[i]>B[j]:
            return self.findKth(A[:i],B[j:],i)
        else:
            return self.findKth(A[i:],B[:j],j)

Log in to reply
 

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