Elegant Python Solution without recursion


  • 0
    K

    class Solution(object):

    def helper(self, nums1, start1,nums2, start2, target):
        start1 = 0
        start2 = 0
        while(1):
    
            #print(start1,start2,target)
            if start1 >= self.l1:
                return nums2[target+start2]
            elif start2 >= self.l2:
                return nums1[target+start1]
    
            if target ==0:
                return min(nums2[start2], nums1[start1])
    
            p1 = min((target-1)//2 + start1, self.l1-1)
            p2 = min((target-1)//2 + start2, self.l2-1)
            v1 = nums1[p1]
            v2 = nums2[p2]
            if v1 <= v2:
                target = target-(p1-start1+1)
                start1= p1+1
            else:
                target = target-(p2-start2+1)
                start2 = p2+1
    
        
    
    
    
    
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        self.l1 = len(nums1)
        self.l2 = len(nums2)
        l1 = self.l1
        l2 = self.l2
        if (l1+l2) % 2 == 1:
            return self.helper(nums1,0,nums2,0,(l1+l2)//2)
        else:
            r = self.helper(nums1,0,nums2,0,(l1+l2)//2) 
            l = self.helper(nums1,0,nums2,0,(l1+l2)//2 -1)
            return (l+r) *1.0/2;

Log in to reply
 

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