LeetCode 4. 寻找两个正序数组的中位数
题目描述
题意分析
给定两个各自按非递减顺序排列的数组，返回全部元素按顺序排列后的中位数。总长度为奇数时，中位数是正中间的一个数；为偶数时，是中间两个数的平均值。重复元素也分别占据一个位置，不能去重。
两个数组可以有一个为空，但不会同时为空。题目要求对数时间复杂度，因此不能先完整合并或重新排序；我们只需要确定中间位置的值，不需要得到整个有序数组。
解法：二分划分较短数组
核心思路
[!blue]
中位数是有序序列的中间边界。设两个数组长度分别为
m、n，合并后的左半部分固定包含leftSize = (m + n + 1) / 2个元素：总长度为偶数时左右一样多，为奇数时左侧多一个。只要左侧所有数都不大于右侧所有数，奇数时取左侧最大值，偶数时取左侧最大值与右侧最小值的平均值。不必真正合并数组。分别从两个数组取一段前缀放入左侧，其余后缀放入右侧。
i表示第一个数组分给左侧的元素个数，j表示第二个数组分给左侧的元素个数；左侧数量固定，因此选择i后，j = leftSize - i也随之确定。切点是元素个数，可以取0或数组长度，并不一定指向一个实际元素。完整有序序列在中间切开后，左侧必然也能表示成这两个数组的前缀，因此一定存在合法划分。每个数组内部已经有序，所以同一数组的左侧元素一定不大于它的右侧元素。剩下只需检查两组交叉边界：
nums1Left <= nums2Right和nums2Left <= nums1Right。这里Left是相应前缀的最后一个数，Right是相应后缀的第一个数。两条不等式同时成立，就能保证整个左半部分不大于整个右半部分。如果
nums1Left > nums2Right，说明第一个数组放到左侧的数太多了。继续增大i会让nums1Left更大或不变，同时让j减小、nums2Right更小或不变，矛盾不可能消失，因此只能减小i。反过来，若nums2Left > nums1Right，说明第一个数组放到左侧的数太少，只能增大i。这种单调性允许在[0, m]中二分切点。先保证第一个数组较短，即
m <= n。此时m <= leftSize <= n，所以任意0 <= i <= m都有0 <= j <= n，另一数组的切点不会越界。某侧没有元素时，左边界用负无穷、右边界用正无穷代替；代码用整数最小值和最大值充当哨兵，统一处理空数组和端点切割。
解题步骤
- 若第一个数组更长，交换两个数组的角色；记较短数组长度为
m，另一个为n。- 固定
leftSize = (m + n + 1) / 2，在闭区间[0, m]中二分i，用j = leftSize - i确定另一个切点。- 读取两个切点左右的四个边界值；空前缀使用负无穷，空后缀使用正无穷。
- 两条交叉不等式均成立时，得到合法划分。总长度为奇数就返回两侧左边界的最大值；为偶数就再取右边界的最小值，求两者平均。
- 若
nums1Left > nums2Right，令right = i - 1；否则是第二条不等式不成立，令left = i + 1，继续二分。
代码实现
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 只在较短数组中选择切点，才能让另一侧划分始终落在合法范围。
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length;
int n = nums2.length;
int leftSize = (m + n + 1) / 2;
int left = 0;
int right = m;
while (left <= right) {
int i = left + (right - left) / 2;
// 左侧总数量固定，较短数组确定划分后另一侧随之确定。
int j = leftSize - i;
int nums1Left = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
int nums1Right = i == m ? Integer.MAX_VALUE : nums1[i];
int nums2Left = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
int nums2Right = j == n ? Integer.MAX_VALUE : nums2[j];
// 数组内部已有序，只需检查两组交叉边界。
if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
int leftMax = Math.max(nums1Left, nums2Left);
if ((m + n) % 2 == 1) {
return leftMax;
}
int rightMin = Math.min(nums1Right, nums2Right);
// 求和之前转换，避免窄整数相加先溢出。
return ((double) leftMax + rightMin) / 2.0;
}
if (nums1Left > nums2Right) {
right = i - 1;
} else {
left = i + 1;
}
}
return 0.0;
}
}
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
// 只在较短数组中选择切点，才能让另一侧划分始终落在合法范围。
if len(nums1) > len(nums2) {
return findMedianSortedArrays(nums2, nums1)
}
m := len(nums1)
n := len(nums2)
leftSize := (m + n + 1) / 2
left := 0
right := m
maxSentinel := int(^uint(0) >> 1)
minSentinel := -maxSentinel - 1
for left <= right {
i := left + (right-left)/2
// 左侧总数量固定，较短数组确定划分后另一侧随之确定。
j := leftSize - i
// 缺失的左邻居用最小值、右邻居用最大值，统一处理边界划分。
nums1Left := minSentinel
nums1Right := maxSentinel
nums2Left := minSentinel
nums2Right := maxSentinel
if i > 0 {
nums1Left = nums1[i-1]
}
if i < m {
nums1Right = nums1[i]
}
if j > 0 {
nums2Left = nums2[j-1]
}
if j < n {
nums2Right = nums2[j]
}
// 数组内部已有序，只需检查两组交叉边界。
if nums1Left <= nums2Right && nums2Left <= nums1Right {
leftMax := maxInt(nums1Left, nums2Left)
if (m+n)%2 == 1 {
return float64(leftMax)
}
rightMin := minInt(nums1Right, nums2Right)
// 求和之前转换，避免整数相加先溢出。
return (float64(leftMax) + float64(rightMin)) / 2.0
}
if nums1Left > nums2Right {
right = i - 1
} else {
left = i + 1
}
}
return 0.0
}
func minInt(a int, b int) int {
if a < b {
return a
}
return b
}
func maxInt(a int, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(\log(m + 1))$，
m为较短数组长度，二分候选切点共m + 1个，每次只比较四个边界值。较短数组为空时为 $O(1)$。- 空间复杂度：$O(1)$，只保存切点和边界值；交换数组角色最多发生一次，不会产生随输入增长的递归栈。
关键点总结
[!green]
- 划分同时满足“左侧数量正确”和“左侧所有值不大于右侧”，才足以确定中位数。
- 数组内部的顺序已由输入保证，只需要核对两组交叉边界。
- 二分调整的是第一个数组贡献给左侧的数量，第二个数组的贡献随之反向变化。
- 较短数组保证另一个切点合法，端点哨兵让空分区沿用同一组比较。
易错点总结
[!yellow]
- 把切点范围写成
[0, m - 1]会漏掉整个数组都放入左侧的情况；切点共有m + 1个。- 未先选择短数组，按
j = leftSize - i得到的下标可能超出第二个数组范围。- 使用左侧最大值作为奇数答案时，左侧必须多一个元素，不能把
leftSize写成(m + n) / 2。- 只检查一组交叉边界，不能保证两个数组合起来仍然左小右大。
- 偶数答案必须用浮点除法，且应在相加前转为浮点数，避免整数求和溢出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 补充题 17. 两个有序数组第 k 小的数 | 困难 | 中位数可转化为一个或两个第k小值查询，复用二分淘汰或分割思路。 |