寻找两个正序数组的中位数
📌 定义
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2，请找出这两个正序数组的中位数。
示例1:
nums1 = [1, 3]
nums2 = [2]
合并后: [1, 2, 3]
中位数: 2
示例2:
nums1 = [1, 2]
nums2 = [3, 4]
合并后: [1, 2, 3, 4]
中位数: (2 + 3) / 2 = 2.5
核心思路
使用二分查找的分治思想，在两个有序数组中找到合适的分割线，使得：
- 左边元素个数 = 右边元素个数（或差1）
- 左边最大值 ≤ 右边最小值
nums1: [1, 3, 5, 7]
nums2: [2, 4, 6, 8]
分割:
nums1_left: [1, 3] | nums1_right: [5, 7]
nums2_left: [2, 4] | nums2_right: [6, 8]
左边最大: max(3, 4) = 4
右边最小: min(5, 6) = 5
中位数 = (4 + 5) / 2 = 4.5
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 合并后排序 | O(m+n) | O(m+n) | 简单但不满足题目要求 |
| 二分查找 | O(log(min(m,n))) | O(1) | 最优解 |
Go 代码
Go 实现
package main
import (
"fmt"
"math"
)
func findMedianSortedArrays(nums1, nums2 []int) float64 {
// 确保nums1是较短的数组
if len(nums1) > len(nums2) {
nums1, nums2 = nums2, nums1
}
m, n := len(nums1), len(nums2)
left, right := 0, m
for left <= right {
partition1 := (left + right) / 2
partition2 := (m + n + 1) / 2 - partition1
maxLeft1 := math.MinInt32
if partition1 > 0 {
maxLeft1 = nums1[partition1-1]
}
maxLeft2 := math.MinInt32
if partition2 > 0 {
maxLeft2 = nums2[partition2-1]
}
minRight1 := math.MaxInt32
if partition1 < m {
minRight1 = nums1[partition1]
}
minRight2 := math.MaxInt32
if partition2 < n {
minRight2 = nums2[partition2]
}
if maxLeft1 <= minRight2 && maxLeft2 <= minRight1 {
if (m+n)%2 == 1 {
return float64(max(maxLeft1, maxLeft2))
}
return float64(max(maxLeft1, maxLeft2)+min(minRight1, minRight2)) / 2.0
} else if maxLeft1 > minRight2 {
right = partition1 - 1
} else {
left = partition1 + 1
}
}
panic("输入数组不合法")
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func main() {
nums1 := []int{1, 3}
nums2 := []int{2}
fmt.Printf("中位数: %.1f\n", findMedianSortedArrays(nums1, nums2))
}思路展开
分割原理
nums1: [1, 3, 5, 7] (m = 4)
nums2: [2, 4, 6, 8, 10, 12] (n = 6)
总长度 = 10，中位数左边应有 5 个元素
二分查找partition1:
partition1 = 2, partition2 = 5 - 2 = 3
nums1: [1, 3] | [5, 7]
nums2: [2, 4, 6] | [8, 10, 12]
检查条件:
max_left1 = 3, min_right2 = 8 → 3 <= 8 ✓
max_left2 = 6, min_right1 = 5 → 6 <= 5 ✗
partition1太小，需要右移
边界情况处理
-
partition在边界：
partition1 = 0：max_left1 = -∞partition1 = m：min_right1 = +∞partition2同理
-
奇偶数长度：
- 奇数：返回左边最大值
- 偶数：返回左边最大值和右边最小值的平均
经典题目
LeetCode 问题
- 寻找两个正序数组的中位数 - LeetCode 4
- 两个有序数组的第K小数
相关问题
- 寻找第K小的元素
- 多个有序数组的中位数
- 数据流中的中位数
⚖️ 优缺点
二分查找法
优点：
- ✅ 时间最优：O(log(min(m,n)))
- ✅ 空间最优：O(1)
- ✅ 满足题目要求：对数时间复杂度
缺点：
- ❌ 实现复杂：边界条件多
- ❌ 理解困难：需要深刻理解二分思想
归并法
优点：
- ✅ 简单直观：易于理解和实现
缺点：
- ❌ 时间复杂度：O(m+n)
- ❌ 空间复杂度：O(m+n)
🎨 应用场景
- 大数据处理：合并两个有序数据集
- 分布式系统：跨节点数据聚合
- 统计分析：快速计算中位数
- 数据库查询：排序合并连接