给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入： nums1 = [1,3], nums2 = [2]
输出： 2.00000
解释： 合并数组 = [1,2,3] ，中位数 2

示例 2：

输入： nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 保证 nums1 是较短的数组（在较短数组上二分，防止越界）
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        m, n = len(nums1), len(nums2)
        total_left = (m + n + 1) // 2  # 左半部分总元素个数
        left, right = 0, m  # 在 nums1 上二分查找分割线位置

        # 二分查找
        while left < right:
            partition1 = (left + right + 1) // 2  # nums1 的切割位置
            partition2 = total_left - partition1   # nums2 的切割位置

            # 如果 nums1 的左侧太大，右移右边界
            if nums1[partition1 - 1] > nums2[partition2]:
                right = partition1 - 1
            else:
                left = partition1

        # 计算最终切割点
        partition1, partition2 = left, total_left - left

        # 分别取出分割线两侧的值（注意越界时取 ±∞）
        max_left_1 = nums1[partition1 - 1] if partition1 > 0 else float('-inf')
        min_right_1 = nums1[partition1] if partition1 < m else float('inf')
        max_left_2 = nums2[partition2 - 1] if partition2 > 0 else float('-inf')
        min_right_2 = nums2[partition2] if partition2 < n else float('inf')

        # 根据总长度奇偶计算中位数
        if (m + n) % 2 == 1:
            # 奇数个元素：中位数是左半部分的最大值
            return max(max_left_1, max_left_2)
        else:
            # 偶数个元素：中位数是左半部分最大与右半部分最小的平均值
            return (max(max_left_1, max_left_2) + min(min_right_1, min_right_2)) / 2