LeetCode【0004】寻找两个正序数组的中位数

本文目录

1 中文题目
2 求解思路
- 2.1 基础解法：合并排序法
- 2.2 优化解法：双指针
- 2.3 最优解法：二分查找
3 题目总结

1 中文题目

给定两个大小分别为 $m$ 和 $n$ 的正序（从小到大）数组 $n u m s 1$ 和 $n u m s 2$ 。请你找出并返回这两个正序数组的中位数。并且算法的时间复杂度应该为 $O (l o g (m + n))$ 。

示例 1：

输入： $n u m s 1 = [1, 3], n u m s 2 = [2]$
输出： $2.00000$
解释：合并数组 = $[1, 2, 3]$ ，中位数 $2$

示例 2：

输入： $n u m s 1 = [1, 2], n u m s 2 = [3, 4]$
输出： $2.50000$
解释：合并数组 = $[1, 2, 3, 4]$ ，中位数 $(2 + 3) /2 = 2.5$

提示：

$\leq nums1.length \leq 1000$
$0\leq nums2.length \leq 1000$
$\leq m + n \leq 2000$
$-10^6 \leq nums1[i], nums2[i] \leq 10^6$

2 求解思路

2.1 基础解法：合并排序法

思路
将两个有序数组合并成一个有序数组，根据合并后数组的长度判断中位数位置，计算并返回中位数

a. 初始化阶段

创建空数组 $m er g e d$ 用于存储合并结果
初始化两个指针 $i$ 和 $j$ 分别指向 $n u m s 1$ 和 $n u m s 2$ 的起始位置

b. 合并阶段

比较 $n u m s 1 [i]$ 和 $n u m s 2 [j]$ 的大小
将较小的元素加入 $m er g e d$ 数组
移动对应的指针
重复直到某个数组遍历完成

c. 处理剩余元素

将未遍历完的数组剩余元素直接加入 $m er g e d$

d. 计算中位数

判断总长度的奇偶性
偶数长度：返回中间两个数的平均值
奇数长度：返回中间的数

Python代码

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:"""寻找两个正序数组的中位数参数:nums1: 第一个有序数组nums2: 第二个有序数组返回:float: 两个数组合并后的中位数"""# 用于存储合并后的有序数组merged = []# 初始化两个数组的指针i, j = 0, 0m, n = len(nums1), len(nums2)# 同时遍历两个数组，比较并合并while i < m and j < n:if nums1[i] <= nums2[j]:# nums1中的元素更小，将其加入mergedmerged.append(nums1[i])i += 1else:# nums2中的元素更小，将其加入mergedmerged.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]) / 2else:# 奇数长度：直接返回中间的数return merged[total_length//2]

时空复杂度分析

时间复杂度： $O (m + n)$
- 合并两个数组需要 $O (m + n)$ 时间
- 访问中位数位置需要 $O (1)$ 时间
空间复杂度： $O (m + n)$

2.2 优化解法：双指针

思路
不需要真正合并数组，只需遍历到中位数位置，使用两个指针交替前进，维护当前值和前一个值

a. 初始化

计算总长度和需要遍历的次数
设置双指针指向两个数组起始位置

b. 遍历过程

比较两个指针指向的值
选择较小值前进
处理数组遍历完的边界情况

c. 结果计算

奇数长度：返回当前值
偶数长度：计算中间两个数的平均值

python代码

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 += 1elif p2 == n:  # nums2已经遍历完current = nums1[p1]p1 += 1elif nums1[p1] <= nums2[p2]:  # nums1当前值更小current = nums1[p1]p1 += 1else:  # nums2当前值更小current = nums2[p2]p2 += 1# 根据总长度的奇偶性返回结果if total_length % 2 == 1:# 奇数长度：直接返回中间值return currentelse:# 偶数长度：返回中间两个数的平均值# 如果当前遍历次数不够，需要再取一个数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)$
- 最多遍历到中位数位置： $(m + n) /2$
- 每次遍历常数操作
- 双指针移动次数： $O ((m + n) /2)$
空间复杂度： $O (1)$
- 双指针：2个整数
- 当前值和前一个值：2个整数
- 其他临时变量：常数个
- 不需要额外数组

2.3 最优解法：二分查找

思路

分割点：将两个数组各自分成左右两部分
平衡条件：左半部分长度等于右半部分（或多1）
正确性条件：左半部分最大值 ≤ 右半部分最小值

查找过程：
（1）在较短数组中二分查找分割点
（2）根据总长度确定另一个数组的分割点
（3）判断分割是否满足条件
（4）调整分割点位置直到找到答案

python代码

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, nums1m, n = len(nums1), len(nums2)# 特殊情况处理：空数组if m == 0:if n % 2 == 0:return (nums2[n//2 - 1] + nums2[n//2]) / 2return nums2[n//2]# 初始化二分查找的范围# left和right表示nums1可能的分割位置left, right = 0, mwhile 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) / 2else:# 奇数个元素：返回左半部分的最大值return max(nums1_left, nums2_left)elif nums1_left > nums2_right:# nums1的分割点太靠右，需要向左移动right = i - 1else:# nums1的分割点太靠左，需要向右移动left = i + 1

时空复杂度分析

时间复杂度分析： $O (l o g (min (m, n)))$
二分查找分析：在较短数组中进行二分查找，每次迭代减少一半搜索空间，迭代次数取决于较短数组长度。具体分析：
- 初始范围： $[0, m] ， m$ 为较短数组长度
- 每次迭代：范围减半
- 迭代次数： $l o g (m)$
- 每次迭代操作： $O (1)$
空间复杂度分析： $O (1)$