4.寻找两个有序数组的中位数

给定两个大小为 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

---

解法

核心方法

分别在num1和num2切割，找到满足Lmax1<Rmin2且Lmax2<Rmin的位置。

奇偶问题

两个数组合并后的长度，有可能是偶数，也有可能是奇数。如果可以让数组长度总是为偶数，那么就可以用公式覆盖。

通过虚拟加入"#"，让每个数组的长度都变成 2x + 1，所以 n+m -> 2n + 2m + 2，恒为偶数。

转换后，原始的元素可以通过新下标//2得到。

比如9，原来是3位，现在是7位， 7//2=3

而对于割，如果‘#’上等于割在2个元素之间，割在数字上等于把数字划到2个部分，总是有以下成立：

LMaxi = (Ci-1)/2 位置上的元素
RMini = Ci/2 位置上的元素

点击查看详细

---

代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        # 使得num2成为更长的表
        if n < m:
            return self.findMedianSortedArrays(nums2, nums1)

        start_pos = 0
        end_pos = 2 * m

        while start_pos <= end_pos:
            c1 = (start_pos + end_pos) // 2
            c2 = m + n - c1  # 因为数组从0开始，所以c1+c2=(m+n+1)-1
            # 切割nums1
            LMax1 = nums1[(c1 - 1) // 2] if c1 > 0 else (-1 * sys.maxsize)
            RMin1 = nums1[c1 // 2] if c1 < 2 * n else sys.maxsize
            # 切割nums2
            LMax2 = nums2[(c2 - 1) // 2] if c2 > 0 else (-1 * sys.maxsize)
            RMin2 = nums2[c2 // 2] if c2 < 2 * m else sys.maxsize
            # 不满足LMax<RMin 则进行调整切割位置
            if LMax1 > RMin2:
                end_pos = c1 - 1
            elif LMax2 > RMin1:
                start_pos = c1 + 1
            else: # 找到合适的c1
                break
		# 返回中位数
        return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0

---

来源

LeetCode中该题地址，Click here!