4. 寻找两个正序数组的中位数
本帖最后由 Gnomeshgh 于 2025-8-21 15:57 编辑一、题目描述
二、解题思路
（一）暴力解
很明显，两个列表都有序，最简单的思路就是合成一个列表然后取中位数。
直接用列表加法进行合并，然后再对合并后的列表进行排序。最后取中位数。
class Solution:
def findMedianSortedArrays(self, nums1: List, nums2: List) -> float:
merged = nums1 + nums2
# 排序
merged.sort()
length = len(merged)
mid = length // 2# 利用整数除法直接获取中间索引
if length % 2 == 1:
return float(merged)
else:
return (merged + merged) / 2.0
进行优化，上面的思路需要合并，但是两个列表长度已知，也就是其实可以计算出中位数在第几个，只需要移动到中位数既可。
可以用两个指针指向两个列表，然后谁小谁移动，保存没有移动的数据，直到移动到中位数。
对于偶数而言还需要保存它的左边的数据，也就是在移动前先保存。
class Solution:
def findMedianSortedArrays(self, nums1: List, nums2: List) -> float:
# 计算两个数组的长度
nums1_len , nums2_len = len(nums1) , len(nums2)
# 计算两个数组的总长度
total =nums1_len + nums2_len
# 初始化两个数组的指针，分别指向起始位置（0索引）
nums1_p = nums2_p = 0
# 用于存储中位数相关的两个元素：
# right存储当前遍历到的元素，left存储上一次遍历到的元素
right = left = 0
# 遍历到中位数位置：总长度//2 + 1次
# 例如总长度5，需要遍历3次（0,1,2位置）；总长度4，需要遍历3次（0,1,2位置）
for _ in range(total // 2 + 1):
# 将当前right的值保存到left（为偶数长度时计算两个中间值的平均做准备）
left = right
# 指针移动逻辑：
# 1. 确保nums1指针未越界
# 2. 两种情况需要移动nums1指针：
# a. nums2指针已越界（nums2遍历完毕）
# b. nums1当前元素小于nums2当前元素（取较小值推进）
if nums1_p < nums1_len and (nums2_p >= nums2_len or nums1 < nums2):
# 更新right为nums1当前元素
right = nums1
# 移动nums1指针到下一位
nums1_p = nums1_p + 1
else:
# 否则移动nums2指针（nums2未遍历完且当前元素更小）
right = nums2
# 移动nums2指针到下一位
nums2_p = nums2_p + 1
# 根据总长度奇偶性返回结果：
# - 偶数：返回中间两个元素的平均值（left和right）
# - 奇数：返回中间元素（right，因为遍历到了中间位置）
return (left + right) / 2.0 if total % 2 == 0 else float(right)
（二）二分法
一般对于有序数组而言会优先想到二分法。
题目求中位数，也就是划分了左右两部分，当是偶数时，左右两部分相等，奇数时，这里让左半部分多1.
也就是在两个数组中找到分割的位置，
假设nums1的分割点为i，（左边有i个，右边有m-i个）
nums2的分割点为j，（左边有j个，右边有n-j个）
当奇数时，即左边最大值就是中间值，此时左半部分是比右半部分多1的
假设总长度为5，则左半部分为3，右半部分为2，此时（m+n+1）// 2 = 3
当为偶数时，左边最大与右边最小之和的二分之一就是中值。
假设总长度为4，则左半部分右半部分都为2，此时（m+n+1）// 2 = 2
所以左半部分总长度的公式为（m+n+1）// 2
因为前半部分是和所以，nums1<nums2，nums2 < nums1
由于已知i就能求出j，所以只需要调整一个就能实现调整两个，
当nums2 > nums1不符合时，也就是左半部分不全小于右半部分，也就是i要增大，也就是left变大，又因为left是闭合的，所以left = i + 1
其它情况就是right变小，又因为right是开区间，所以right = i
然后不断的向中值逼近，直到退出循环找到最佳的中值位置
class Solution:
def findMedianSortedArrays(self, nums1: List, nums2: List) -> float:
# 1. 确保在较短的数组上进行二分查找，减少二分次数，优化时间复杂度
# 因为二分查找的时间复杂度取决于数组长度，短数组的log值更小
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
# 2. 定义基本变量
m, n = len(nums1), len(nums2)# m为较短数组长度，n为较长数组长度
left, right = 0, m# 二分查找的边界：nums1的分割点i的可能范围（0~m）
# 左半部分总长度：确保左半元素数量 ≥ 右半（奇数时多1，偶数时相等）
total_left_length = (m + n + 1) // 2# 公式统一奇数和偶数情况
# 3. 二分查找寻找最优分割点i
# 目标：找到i使得nums1和nums2的左半部分所有元素 ≤ 右半部分所有元素
while left < right:
# 计算当前分割点i（向下取整，配合后续逻辑避免死循环）
i = (left + right) // 2
# 计算nums2的分割点j：左半总长度固定，j由i决定
j = total_left_length - i
# 判断当前i是否需要右移：
# nums1是nums1右半的最小值，nums2是nums2左半的最大值
# 若nums1右半最小值 < nums2左半最大值，说明i太小（nums1左半需包含更多元素）
if nums1 < nums2:
left = i + 1# 右移i，同时保证范围缩小（避免死循环）
else:
# 否则i可能过大，左移分割点
right = i
# 4. 确定最终分割点i和j
i , j = left , total_left_length - left
# 5. 计算左半部分的最大值（中位数的左边界）
# 处理边界情况：某一数组的左半部分为空
if i == 0:
# nums1左半为空，左半最大值只能来自nums2的左半
max_left = nums2
elif j == 0:
# nums2左半为空，左半最大值只能来自nums1的左半
max_left = nums1
else:
# 正常情况：取两个数组左半部分的最大值
max_left = max(nums1, nums2)
# 6. 若总长度为奇数，中位数就是左半部分的最大值（左半比右半多1个元素）
if (m + n ) % 2 == 1:
return float(max_left)
# 7. 若总长度为偶数，还需计算右半部分的最小值（中位数的右边界）
# 处理边界情况：某一数组的右半部分为空
if i == m:
# nums1右半为空，右半最小值只能来自nums2的右半
min_right = nums2
elif j == n:
# nums2右半为空，右半最小值只能来自nums1的右半
min_right = nums1
else:
# 正常情况：取两个数组右半部分的最小值
min_right = min(nums1, nums2)
# 8. 偶数长度时，中位数是左半最大值和右半最小值的平均值
return (max_left + min_right) / 2
为了找到两个正序数组的中位数并要求时间复杂度为 O(log(m+n))，我们可以使用二分查找的方法。核心思想是将两个数组分割成左右两部分，使得左半部分的所有元素都小于或等于右半部分的所有元素，然后根据总长度的奇偶性计算中位数。
### 方法思路
1. **确保 nums1 是较短的数组**：这样二分查找的范围更小，效率更高。
2. **计算总长度 total**：total = m + n。
3. **确定左半部分的大小**：left_size = (total + 1) // 2（向上取整）。
4. **在 nums1 上使用二分查找**：找到分割点 i，使得 nums1 的左半部分和 nums2 的左半部分合并后，左半部分的最大值小于等于右半部分的最小值。
5. **调整分割点**：通过比较 nums1 和 nums2 以及 nums2 和 nums1 来调整 i。
6. **计算中位数**：根据总长度的奇偶性，取左半部分的最大值和右半部分的最小值（或平均值）。
### 解决代码
def findMedianSortedArrays(nums1, nums2):
# 确保 nums1 是较短的数组
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total = m + n
left_size = (total + 1) // 2# 左半部分的大小（向上取整）
# 在 nums1 上使用二分查找
low, high = 0, m
while low <= high:
i = (low + high) // 2# nums1 的分割点
j = left_size - i # nums2 的分割点
# 处理边界情况
nums1_left_max = float('-inf') if i == 0 else nums1
nums1_right_min = float('inf') if i == m else nums1
nums2_left_max = float('-inf') if j == 0 else nums2
nums2_right_min = float('inf') if j == n else nums2
# 检查分割是否正确
if nums1_left_max <= nums2_right_min and nums2_left_max <= nums1_right_min:
# 分割正确，计算中位数
if total % 2 == 1:
return max(nums1_left_max, nums2_left_max)
else:
return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2.0
elif nums1_left_max > nums2_right_min:
high = i - 1# i 太大，减小 i
else:
low = i + 1 # i 太小，增大 i
return 0.0# 不会执行到这里，但为了语法完整
### 代码解释
- **确保 nums1 较短**：交换数组以使二分查找更高效。
- **计算 left_size**：左半部分的大小为总长度加一后除以二（向上取整）。
- **二分查找分割点 i**：在 nums1 上调整 i，使得左半部分的最大值小于等于右半部分的最小值。
- **处理边界**：当 i 或 j 为 0 或数组长度时，使用无穷大或负无穷大避免索引错误。
- **计算中位数**：根据总长度奇偶性，返回左半部分最大值或左右部分最大最小值的平均值。
这种方法确保了时间复杂度为 O(log(min(m, n)))，符合要求。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 {:13_413:}{:13_413:}{:13_413:} 可以哇，学习了 看不懂 gpa5031 发表于 2025-8-22 08:39
看不懂
哪里看不懂，你说说，我在改一改
页:
[1]