O(log(min(m, n, k))) solution with binary search


  • 0

    It's similar to @StefanPochmann's solution, but more generic and straightforward. Its goal is to find the first element in nums1 meeting max(nums1[p], nums2[k-p-2]) <= min(nums1[p+1], nums2[k-p-1]).

    class Solution(object):
        def get(self, nums, p):
            if p < 0:
                return float('-inf')
    
            if p >= len(nums):
                return float('inf')
    
            return nums[p]
    
        def meeting(self, nums1, nums2, p1, p2):
            return max(self.get(nums1, p1), self.get(nums2, p2)) <= min(
                self.get(nums1, p1 + 1), self.get(nums2, p2 + 1))
    
        def findKth(self, nums1, nums2, k):
            low, high = 0, min(k, len(nums1)) - 1
    
            while low <= high:
                p1 = low + high >> 1
                p2 = k - p1 - 2
    
                # if it's the first element in nums1 meeting
                # max(nums1[p], nums2[k-p-2]) <= min(nums1[p+1], nums2[k-p-1])
                if self.meeting(nums1, nums2, p1, p2) and (
                        p1 == 0 or not self.meeting(nums1, nums2, p1-1, p2+1)):
                    return max(nums1[p1], self.get(nums2, p2))
    
                if self.get(nums2, p2) > self.get(nums1, p1 + 1):
                    low = p1 + 1
                else:
                    high = p1 - 1
    
            return nums2[k - 1]
    
        def findMedianSortedArrays(self, nums1, nums2):
            m, n = map(len, (nums1, nums2))
            if m > n:
                return self.findMedianSortedArrays(nums2, nums1)
    
            half = m + n >> 1
    
            if (m + n) & 1:
                return self.findKth(nums1, nums2, half + 1)
    
            return (
                self.findKth(nums1, nums2, half) +
                self.findKth(nums1, nums2, half + 1)
            ) / 2.0
    

Log in to reply
 

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