leetcode [4] 寻找两个有序数组的中位数

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        len1, len2 = len(nums1), len(nums2)
        left = (len1 + len2 + 1) // 2
        right = (len1 + len2 + 2) // 2
        return (self.getK(nums1, 0, len1 - 1, nums2, 0, len2 - 1, left)
        + self.getK(nums1, 0, len1 - 1, nums2, 0, len2 - 1, right)) / 2

    def getK(self, nums1, start1, end1, nums2, start2, end2, k):
        len1 = end1 - start1 + 1
        len2 = end2 - start2 + 1
        if len1 > len2:
            return self.getK(nums2, start2, end2, nums1, start1, end1, k)
        if len1 == 0:
            return nums2[start2 + k - 1]

        if k == 1:
            return min(nums1[start1], nums2[start2])
        i = start1 + min(len1, k // 2) - 1
        j = start2 + min(len2, k // 2) - 1
        if nums1[i] > nums2[j]:
            return self.getK(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1))
        else:
            return self.getK(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1))

另外一个方法，比较清晰，来自题解:

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        leng1 = len(nums1)
        leng2 = len(nums2)
        if leng1 > leng2:
            return self.findMedianSortedArrays(nums2,nums1)
        mid = (leng1 + leng2 + 1) // 2
        left, right = 0, leng1
        while left < right :
            mid1 = (right + left) // 2
            mid2 = mid - mid1
            if nums1[mid1] < nums2[mid2 - 1]:
                left = mid1 + 1
            else:
                right = mid1
        mid1 = left
        mid2 = mid - mid1 
        ans1 = max(nums1[mid1 - 1] if mid1 > 0 else float("-inf"), nums2[mid2 - 1] if mid2 > 0 else float("-inf"))
        if (leng1 + leng2) % 2 == 1:
            return ans1
        ans2 = min(nums1[mid1] if mid1 < leng1 else float("inf"), nums2[mid2] if mid2 < leng2 else float("inf"))
        return (ans1 + ans2) / 2