您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
# 如何实现寻找两个正序数组的中位数
## 引言
在算法和数据结构领域，寻找两个有序数组的中位数是一个经典问题。这个问题看似简单，但要在最优时间复杂度内解决却需要巧妙的算法设计。本文将深入探讨该问题的多种解法，从暴力法到最优化的二分查找法，逐步分析其原理和实现细节。
## 问题描述
给定两个大小分别为 `m` 和 `n` 的正序（非递减）数组 `nums1` 和 `nums2`，请找出这两个正序数组的中位数，并要求算法的时间复杂度为 `O(log(m+n))`。
**示例1：**
nums1 = [1, 3] nums2 = [2] 中位数是 2.0
**示例2：**
nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5
## 方法一：暴力合并法（时间复杂度 O(m+n)）
### 算法思路
1. 合并两个有序数组
2. 根据合并后数组长度的奇偶性计算中位数
### 代码实现
```python
def findMedianSortedArrays(nums1, nums2):
merged = []
i = j = 0
m, n = len(nums1), len(nums2)
while i < m and j < n:
if nums1[i] < nums2[j]:
merged.append(nums1[i])
i += 1
else:
merged.append(nums2[j])
j += 1
merged.extend(nums1[i:])
merged.extend(nums2[j:])
length = len(merged)
if length % 2 == 1:
return merged[length // 2]
else:
return (merged[length // 2 - 1] + merged[length // 2]) / 2
不需要实际合并数组，只需用两个指针找到中位数的位置
def findMedianSortedArrays(nums1, nums2):
m, n = len(nums1), len(nums2)
total = m + n
prev = curr = 0
i = j = 0
for _ in range(total // 2 + 1):
prev = curr
if i < m and (j >= n or nums1[i] < nums2[j]):
curr = nums1[i]
i += 1
else:
curr = nums2[j]
j += 1
return curr if total % 2 == 1 else (prev + curr) / 2
将问题转化为寻找第k小的元素，通过二分查找快速排除不可能的部分
nums1 是较短的数组nums1 中进行二分查找，确定分割线位置def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total = m + n
half = total // 2
left, right = 0, m - 1
while True:
i = (left + right) // 2 # nums1的分割线
j = half - i - 2 # nums2的分割线
nums1_left = nums1[i] if i >= 0 else float('-inf')
nums1_right = nums1[i+1] if (i+1) < m else float('inf')
nums2_left = nums2[j] if j >= 0 else float('-inf')
nums2_right = nums2[j+1] if (j+1) < n else float('inf')
if nums1_left <= nums2_right and nums2_left <= nums1_right:
if total % 2 == 1:
return min(nums1_right, nums2_right)
else:
return (max(nums1_left, nums2_left) + min(nums1_right, nums2_right)) / 2
elif nums1_left > nums2_right:
right = i - 1
else:
left = i + 1
将问题转化为寻找两个有序数组的第k小元素，通过递归不断缩小问题规模
def findMedianSortedArrays(nums1, nums2):
def getKth(k):
index1, index2 = 0, 0
while True:
if index1 == m:
return nums2[index2 + k - 1]
if index2 == n:
return nums1[index1 + k - 1]
if k == 1:
return min(nums1[index1], nums2[index2])
newIndex1 = min(index1 + k // 2 - 1, m - 1)
newIndex2 = min(index2 + k // 2 - 1, n - 1)
pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
if pivot1 <= pivot2:
k -= newIndex1 - index1 + 1
index1 = newIndex1 + 1
else:
k -= newIndex2 - index2 + 1
index2 = newIndex2 + 1
m, n = len(nums1), len(nums2)
total = m + n
if total % 2 == 1:
return getKth((total + 1) // 2)
else:
return (getKth(total // 2) + getKth(total // 2 + 1)) / 2
空数组处理：
if not nums1:
return nums2[n//2] if n%2==1 else (nums2[n//2-1]+nums2[n//2])/2
数组有重叠元素：
所有元素相同：
nums1 = [2,2], nums2 = [2,2] 应返回2.0| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力合并法 | O(m+n) | O(m+n) | 小规模数据，简单实现 |
| 双指针法 | O(m+n) | O(1) | 中等规模数据 |
| 二分查找法 | O(log(min(m,n))) | O(1) | 大规模数据，最优解 |
| 递归分治法 | O(log(m+n)) | O(1) | 理论分析，教学示例 |
本文详细探讨了四种不同效率的解决方案，从直观的暴力法到最优的二分查找法。在实际应用中，应根据数据规模选择合适的方法：
最终的最优解将时间复杂度降到了O(log(min(m,n)))，这是通过充分利用数组有序性质和对问题本质的深刻理解实现的。
”`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。