1 中文题目
给定两个大小分别为 m m m 和 n n n 的正序（从小到大）数组 n u m s 1 nums1 nums1 和 n u m s 2 nums2 nums2。请你找出并返回这两个正序数组的 。并且算法的时间复杂度应该为 O ( l o g ( m + n ) ) O(log (m+n)) O(log(m+n)) 。
示例 1：
- 输入： n u m s 1 = [ 1 , 3 ] , n u m s 2 = [ 2 ] nums1 = [1,3], nums2 = [2] nums1=[1,3],nums2=[2]
- 输出： 2.00000 2.00000 2.00000
- 解释：合并数组 = [ 1 , 2 , 3 ] [1,2,3] [1,2,3] ，中位数 2 2 2
示例 2：
- 输入： n u m s 1 = [ 1 , 2 ] , n u m s 2 = [ 3 , 4 ] nums1 = [1,2], nums2 = [3,4] nums1=[1,2],nums2=[3,4]
- 输出： 2.50000 2.50000 2.50000
- 解释：合并数组 = [ 1 , 2 , 3 , 4 ] [1,2,3,4] [1,2,3,4] ，中位数 ( 2 + 3 ) / 2 = 2.5 (2 + 3) / 2 = 2.5 (2+3)/2=2.5
提示：
- 0 ≤ n u m s 1. l e n g t h ≤ 1000 0 \leq nums1.length \leq 1000 0≤nums1.length≤1000
- 0 ≤ n u m s 2. l e n g t h ≤ 1000 0\leq nums2.length \leq 1000 0≤nums2.length≤1000
- 1 ≤ m + n ≤ 2000 1 \leq m + n \leq 2000 1≤m+n≤2000
- − 1 0 6 ≤ n u m s 1 [ i ] , n u m s 2 [ i ] ≤ 1 0 6 -10^6 \leq nums1[i], nums2[i] \leq 10^6 −106≤nums1[i],nums2[i]≤106
2 求解思路
2.1 基础解法：合并排序法
将两个有序数组合并成一个有序数组，根据合并后数组的长度判断中位数位置，计算并返回中位数
a. 初始化阶段
- 创建空数组 m e r g e d merged merged用于存储合并结果
- 初始化两个指针 i i i和 j j j分别指向 n u m s 1 nums1 nums1和 n u m s 2 nums2 nums2的起始位置
b. 合并阶段
- 比较 n u m s 1 [ i ] nums1[i] nums1[i]和 n u m s 2 [ j ] nums2[j] nums2[j]的大小
- 将较小的元素加入 m e r g e d merged merged数组
- 移动对应的指针
- 重复直到某个数组遍历完成
c. 处理剩余元素
- 将未遍历完的数组剩余元素直接加入 m e r g e d merged merged
d. 计算中位数
- 判断总长度的奇偶性
- 偶数长度：返回中间两个数的平均值
- 奇数长度：返回中间的数
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
"""
寻找两个正序数组的中位数
参数:
nums1: 第一个有序数组
nums2: 第二个有序数组
返回:
float: 两个数组合并后的中位数
"""
# 用于存储合并后的有序数组
merged = []
# 初始化两个数组的指针
i, j = 0, 0
m, n = len(nums1), len(nums2)
# 同时遍历两个数组，比较并合并
while i < m and j < n:
if nums1[i] <= nums2[j]:
# nums1中的元素更小，将其加入merged
merged.append(nums1[i])
i += 1
else:
# nums2中的元素更小，将其加入merged
merged.append(nums2[j])
j += 1
# 处理剩余元素
# 如果nums1还有剩余元素
while i < m:
merged.append(nums1[i])
i += 1
# 如果nums2还有剩余元素
while j < n:
merged.append(nums2[j])
j += 1
# 计算合并后数组的总长度
total_length = m + n
# 判断总长度的奇偶性并计算中位数
if total_length % 2 == 0:
# 偶数长度：取中间两个数的平均值
return (merged[total_length//2-1] + merged[total_length//2]) / 2
else:
# 奇数长度：直接返回中间的数
return merged[total_length//2]
- 时间复杂度： O ( m + n ) O(m + n) O(m+n)
- 合并两个数组需要 O ( m + n ) O(m + n) O(m+n)时间
- 访问中位数位置需要 O ( 1 ) O(1) O(1)时间
- 空间复杂度： O ( m + n ) O(m + n) O(m+n)
2.2 优化解法：双指针
不需要真正合并数组，只需遍历到中位数位置，使用两个指针交替前进，维护当前值和前一个值
a. 初始化
- 计算总长度和需要遍历的次数
- 设置双指针指向两个数组起始位置
b. 遍历过程
- 比较两个指针指向的值
- 选择较小值前进
- 处理数组遍历完的边界情况
c. 结果计算
- 奇数长度：返回当前值
- 偶数长度：计算中间两个数的平均值
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
"""
使用双指针法查找两个有序数组的中位数
算法思路：
1. 使用两个指针分别遍历两个数组
2. 按顺序合并两个数组的元素，直到达到中位数位置
3. 根据总长度的奇偶性返回中位数
参数:
nums1: 第一个有序数组
nums2: 第二个有序数组
返回:
float: 两个数组合并后的中位数
"""
# 获取两个数组的长度
m, n = len(nums1), len(nums2)
total_length = m + n
# 计算需要遍历的次数
# 如果总长度为奇数，需要遍历到中间位置
# 如果总长度为偶数，需要遍历到中间两个数
k = (total_length + 1) // 2
# 定义双指针，分别指向两个数组的起始位置
p1 = p2 = 0
# 记录当前值和前一个值
# 用于计算偶数长度时的平均值
current = previous = 0
# 遍历直到达到中位数位置
for _ in range(k):
# 保存前一个值
previous = current
# 处理边界情况和比较大小
if p1 == m: # nums1已经遍历完
current = nums2[p2]
p2 += 1
elif p2 == n: # nums2已经遍历完
current = nums1[p1]
p1 += 1
elif nums1[p1] <= nums2[p2]: # nums1当前值更小
current = nums1[p1]
p1 += 1
else: # nums2当前值更小
current = nums2[p2]
p2 += 1
# 根据总长度的奇偶性返回结果
if total_length % 2 == 1:
# 奇数长度：直接返回中间值
return current
else:
# 偶数长度：返回中间两个数的平均值
# 如果当前遍历次数不够，需要再取一个数
if p1 == m: # nums1已经遍历完
next_value = nums2[p2]
elif p2 == n: # nums2已经遍历完
next_value = nums1[p1]
else: # 比较两个数组当前值
next_value = min(nums1[p1], nums2[p2])
return (current + next_value) / 2
- 时间复杂度： O ( m + n ) O(m+n) O(m+n)
- 最多遍历到中位数位置： ( m + n ) / 2 (m+n)/2 (m+n)/2
- 每次遍历常数操作
- 双指针移动次数： O ( ( m + n ) / 2 ) O((m+n)/2) O((m+n)/2)
- 空间复杂度： O ( 1 ) O(1) O(1)
- 双指针：2个整数
- 当前值和前一个值：2个整数
- 其他临时变量：常数个
- 不需要额外数组
2.3 最优解法：二分查找
- 分割点：将两个数组各自分成左右两部分
- 平衡条件：左半部分长度等于右半部分（或多1）
- 正确性条件：左半部分最大值 ≤ 右半部分最小值
查找过程：
（1）在较短数组中二分查找分割点
（2）根据总长度确定另一个数组的分割点
（3）判断分割是否满足条件
（4）调整分割点位置直到找到答案
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
"""
使用分治法查找两个有序数组的中位数
核心思想：
1. 将数组分成左右两部分，使得左部分的长度等于右部分
2. 保证左部分的最大值小于等于右部分的最小值
3. 通过二分查找确定分割点
参数:
nums1: 第一个有序数组
nums2: 第二个有序数组
返回:
float: 两个数组合并后的中位数
"""
# 确保 nums1 是较短的数组，优化查找过程
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
# 特殊情况处理：空数组
if m == 0:
if n % 2 == 0:
return (nums2[n//2 - 1] + nums2[n//2]) / 2
return nums2[n//2]
# 初始化二分查找的范围
# left和right表示nums1可能的分割位置
left, right = 0, m
while left <= right:
# 在nums1中找分割点
i = (left + right) // 2
# nums2的分割点由nums1的分割点决定
# 确保左右两部分长度相等或左部分多一个
j = (m + n + 1) // 2 - i
# 获取分割点左右的值
# 使用无穷大和无穷小处理边界情况
nums1_left = float('-inf') if i == 0 else nums1[i-1]
nums1_right = float('inf') if i == m else nums1[i]
nums2_left = float('-inf') if j == 0 else nums2[j-1]
nums2_right = float('inf') if j == n else nums2[j]
# 判断分割是否合适
if nums1_left <= nums2_right and nums2_left <= nums1_right:
# 找到合适的分割点
# 根据总长度的奇偶性返回结果
if (m + n) % 2 == 0:
# 偶数个元素：返回左半部分最大值和右半部分最小值的平均值
left_max = max(nums1_left, nums2_left)
right_min = min(nums1_right, nums2_right)
return (left_max + right_min) / 2
else:
# 奇数个元素：返回左半部分的最大值
return max(nums1_left, nums2_left)
elif nums1_left > nums2_right:
# nums1的分割点太靠右，需要向左移动
right = i - 1
else:
# nums1的分割点太靠左，需要向右移动
left = i + 1
- 时间复杂度分析： O ( l o g ( m i n ( m , n ) ) ) O(log(min(m,n))) O(log(min(m,n)))
二分查找分析：在较短数组中进行二分查找，每次迭代减少一半搜索空间，迭代次数取决于较短数组长度。具体分析：- 初始范围： [ 0 , m ] ， m [0, m]，m [0,m]，m为较短数组长度
- 每次迭代：范围减半
- 迭代次数： l o g ( m ) log(m) log(m)
- 每次迭代操作： O ( 1 ) O(1) O(1)
- 空间复杂度分析： O ( 1 ) O(1) O(1)
3 题目总结