0004. Median of Two Sorted Arrays¶
题目信息¶
- 题号:
寻找两个正序数组的中位数
- 难度:
Hard
- 主题:
数组、二分查找、分割、边界哨兵
- 原题:
- 重点:
从归并两个有序数组,推导到搜索左右两部分的合法分割,并把线性扫描降为较短数组上的二分查找
题目重述¶
给定两个分别按非递减顺序排列的整数数组 nums1 和 nums2,需要返回把两者全部元素合并并保持有序后得到的中位数。
设两数组长度分别为 m 和 n。其中一个数组可以为空,但两者不能同时为空。总长度为奇数时,中位数是合并序列正中间的元素;总长度为偶数时,中位数是中间两个元素的平均值。题目要求算法达到 O(log(m + n)) 时间复杂度。
约束条件:
0 <= m, n <= 1000;1 <= m + n <= 2000;-10^6 <= nums1[i], nums2[i] <= 10^6。
自建示例¶
奇数总长度:
nums1 = [1, 4]、nums2 = [2, 3, 8],合并后为[1, 2, 3, 4, 8],返回3.0;偶数总长度:
nums1 = [1, 2, 8]、nums2 = [3, 4, 5, 6, 7],中间两个数为4和5,返回4.5;一侧为空:
nums1 = []、nums2 = [2, 4, 6, 8],返回5.0;大小关系交错:
nums1 = [1, 10]、nums2 = [2, 3, 4, 5, 6],合法分割不能只按数组长度平均切开,返回4.0;含重复值:
nums1 = [1, 2, 2]、nums2 = [2, 2, 3],返回2.0。
C++ 实现¶
#include <algorithm>
#include <limits>
#include <vector>
class Solution {
private:
double mergeAll(const std::vector<int>& nums1, const std::vector<int>& nums2) {
std::vector<int> merged;
merged.reserve(nums1.size() + nums2.size());
int i = 0;
int j = 0;
while (i < static_cast<int>(nums1.size()) || j < static_cast<int>(nums2.size())) {
if (j == static_cast<int>(nums2.size()) || (i < static_cast<int>(nums1.size()) && nums1[i] <= nums2[j])) {
merged.push_back(nums1[i++]);
} else {
merged.push_back(nums2[j++]);
}
}
const int total = static_cast<int>(merged.size());
const int middle = total / 2;
if (total % 2 == 1) {
return merged[middle];
}
return (static_cast<double>(merged[middle - 1]) + static_cast<double>(merged[middle])) / 2.0;
}
double walkToMiddle(const std::vector<int>& nums1, const std::vector<int>& nums2) {
const int total = static_cast<int>(nums1.size() + nums2.size());
const int middle = total / 2;
int i = 0;
int j = 0;
int previous = 0;
int current = 0;
for (int step = 0; step <= middle; ++step) {
previous = current;
if (j == static_cast<int>(nums2.size()) || (i < static_cast<int>(nums1.size()) && nums1[i] <= nums2[j])) {
current = nums1[i++];
} else {
current = nums2[j++];
}
}
if (total % 2 == 1) {
return current;
}
return (static_cast<double>(previous) + static_cast<double>(current)) / 2.0;
}
double binaryPartition(const std::vector<int>& nums1, const std::vector<int>& nums2) {
if (nums1.size() > nums2.size()) {
return binaryPartition(nums2, nums1);
}
const int m = static_cast<int>(nums1.size());
const int n = static_cast<int>(nums2.size());
const int leftSize = (m + n + 1) / 2;
int low = 0;
int high = m;
while (low <= high) {
const int cut1 = low + (high - low) / 2;
const int cut2 = leftSize - cut1;
const long long left1 = cut1 == 0 ? std::numeric_limits<long long>::lowest() : nums1[cut1 - 1];
const long long right1 = cut1 == m ? std::numeric_limits<long long>::max() : nums1[cut1];
const long long left2 = cut2 == 0 ? std::numeric_limits<long long>::lowest() : nums2[cut2 - 1];
const long long right2 = cut2 == n ? std::numeric_limits<long long>::max() : nums2[cut2];
if (left1 <= right2 && left2 <= right1) {
const long long leftMax = std::max(left1, left2);
if ((m + n) % 2 == 1) {
return static_cast<double>(leftMax);
}
const long long rightMin = std::min(right1, right2);
return (static_cast<double>(leftMax) + static_cast<double>(rightMin)) / 2.0;
}
if (left1 > right2) {
high = cut1 - 1;
} else {
low = cut1 + 1;
}
}
return 0.0;
}
public:
double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
return binaryPartition(nums1, nums2);
}
};
题解¶
完整归并¶
两个输入数组各自有序,最直接的方法是按照归并排序的合并阶段,从两个数组头部反复取出较小元素,构造完整有序数组。
设合并后的总长度为 total。若 total 为奇数,中位数位于下标 total / 2;若为偶数,中间位置为 total / 2 - 1 和 total / 2。
mergeAll 把全部元素写入 merged 后直接读取这些位置。它清楚地复现了中位数定义,问题在于无论中位数多早能够确定,仍会访问并保存全部 m + n 个元素。
中位位置截断¶
中位数只依赖合并序列的前半部分。继续沿用双指针归并时,不必构造完整数组,只需取出到下标 total / 2 为止。
walkToMiddle 使用 previous 和 current 保存最近取出的两个值。总长度为奇数时,current 就是中位数;总长度为偶数时,答案是 previous 与 current 的平均值。
这一步删除了 merged 数组,把工作空间从 O(m + n) 降为 O(1)。时间仍为线性,因为算法依旧逐个生成中位位置之前的元素,没有把两个数组的有序性转化为可二分的搜索条件。
分割模型¶
要跳过大量元素,需要从“生成合并序列”改为“直接确定中位数两侧的边界”。在两个数组中分别选择分割位置 cut1 和 cut2:
nums1: 左侧 cut1 个元素 | 右侧剩余元素
nums2: 左侧 cut2 个元素 | 右侧剩余元素
令合并后左侧元素数量为 leftSize = (m + n + 1) / 2,于是 cut2 = leftSize - cut1。只要搜索 cut1,另一条分割线就被唯一确定。
公式中的 +1 统一了奇偶情况:总长度为偶数时左右数量相同;总长度为奇数时左侧比右侧多一个元素,中位数就落在左侧最大值上。
合法分割¶
每个数组内部已经有序,所以只需观察分割线附近四个值:
left1 = nums1 左侧最大值
right1 = nums1 右侧最小值
left2 = nums2 左侧最大值
right2 = nums2 右侧最小值
左侧全部元素都不大于右侧全部元素,当且仅当两个跨数组条件同时成立:left1 <= right2 且 left2 <= right1。
条件成立后,合并左侧最大值为 max(left1, left2),合并右侧最小值为 min(right1, right2)。奇数总长度直接返回左侧最大值;偶数总长度返回左右两个边界值的平均数。算法不需要知道左右两部分内部的完整排列。
分割线位于数组端点时,某一侧可能没有真实元素。代码把空左侧边界视为负无穷,把空右侧边界视为正无穷,使端点候选仍能使用同一组比较条件。一侧数组为空的情况也因此自然包含在主循环中。
较短数组二分¶
主解法始终在较短数组上搜索 cut1。设其长度为 m,另一数组长度为 n,并保证 m <= n。此时 cut1 在 [0, m] 中变化时,由 cut2 = leftSize - cut1 得到的分割位置始终位于 [0, n],无需额外裁剪第二个数组的边界。
若 left1 > right2,说明 nums1 左侧取入的元素过多,分割线必须左移,因此令 high = cut1 - 1。
剩余的不合法情况只能是 left2 > right1,说明 nums1 左侧取入的元素过少,分割线必须右移,因此令 low = cut1 + 1。
有序性保证这两个方向具有单调性:cut1 增大时,left1 不会减小,right1 不会减小,而 cut2 同时减小,left2 和 right2 不会增大。因此一次比较就能排除一半候选分割位置。
状态推演¶
以 nums1 = [1, 2, 8]、nums2 = [3, 4, 5, 6, 7] 为例,总长度为 8,leftSize = 4:
轮次 |
|
|
左边界 |
右边界 |
处理 |
|---|---|---|---|---|---|
1 |
1 |
3 |
|
|
|
2 |
2 |
2 |
|
|
合法分割 |
合法分割的左侧包含 [1, 2] 和 [3, 4],左侧最大值为 4;右侧包含 [8] 和 [5, 6, 7],右侧最小值为 5。总长度为偶数,所以答案为 (4 + 5) / 2 = 4.5。
代码演进¶
mergeAll 使用双指针生成完整有序数组,代码直接对应中位数定义,但保存了最终答案不需要的后半部分。
walkToMiddle 删除结果数组和后半段归并,只维护最近两个值。空间降为常数,但两个指针仍需要逐个跨过前半部分元素。
binaryPartition 不再生成任何合并元素,而是把中位位置转换为左右分割数量,再通过四个边界值判断分割是否合法。双指针、逐元素选择和临时合并结果全部消失,搜索对象从 m + n 个元素变成较短数组中的 m + 1 个分割位置。
公开入口采用 binaryPartition,因为它满足题目的对数时间要求,同时保持 O(1) 工作空间。
复杂度分析¶
方法 |
时间复杂度 |
工作空间 |
主要代价 |
|---|---|---|---|
完整归并 |
|
|
生成并保存全部合并元素 |
中位截断 |
|
|
逐个生成前半部分元素 |
二分分割 |
|
|
搜索较短数组中的合法分割位置 |
边界处理¶
一侧数组为空时,负无穷和正无穷哨兵让分割条件仍然成立;
总长度为奇数时,左侧故意多保留一个元素,直接返回左侧最大值;
总长度为偶数时,先把两个中间值转换为
double再相加,避免整数平均造成截断;数组中存在重复值时,合法条件使用
<=,相等元素可以分布在分割线两侧;主解法只读取输入数组,不修改其内容。