寻找两个正序数组的中位数
Median of Two Sorted Arrays
本机进度仅保存在当前浏览器
题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2，请你找出并返回这两个正序数组的「中位数」。要求算法的时间复杂度为 O(log(m + n))。
示例：nums1 = [1, 3]，nums2 = [2]，输出 2.0；nums1 = [1, 2]，nums2 = [3, 4]，输出 2.5。
解题思路
- 中位数本质是把全部元素分成数量相等（或多一）的两组，且左组最大值 <= 右组最小值。
- 在较短数组上枚举分割线 i（取 0..m），较长数组的分割线 j 由总数约束 j = (m + n + 1) // 2 - i 直接确定。
- 合法性只需检查边界：nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]，不满足时二分调整 i。
- 总数为奇数时中位数是左组最大值；偶数时取左组最大与右组最小的平均。对 i=0 或 i=m 等边界用正无穷哨兵处理。
参考实现
查看参考实现Python · 建议先自行作答
def findMedianSortedArrays(nums1, nums2):
# 始终在较短数组上二分分割线
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2
j = half - i
# 边界哨兵：分割线外侧视为正/负无穷
l1 = nums1[i - 1] if i > 0 else float('-inf')
r1 = nums1[i] if i < m else float('inf')
l2 = nums2[j - 1] if j > 0 else float('-inf')
r2 = nums2[j] if j < n else float('inf')
if l1 <= r2 and l2 <= r1:
if (m + n) % 2:
return max(l1, l2)
return (max(l1, l2) + min(r1, r2)) / 2
if l1 > r2:
hi = i - 1
else:
lo = i + 1
raise ValueError('输入不是有序数组')