0004. Median of Two Sorted Arrays
=================================
题目信息
--------
:题号: 0004. 寻找两个正序数组的中位数
:难度: Hard
:主题: 数组、二分查找、分割、边界哨兵
:原题: `LeetCode 0004 `_
:重点: 从归并两个有序数组,推导到搜索左右两部分的合法分割,并把线性扫描降为较短数组上的二分查找
题目重述
--------
给定两个分别按非递减顺序排列的整数数组 ``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++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
double mergeAll(const std::vector& nums1, const std::vector& nums2) {
std::vector merged;
merged.reserve(nums1.size() + nums2.size());
int i = 0;
int j = 0;
while (i < static_cast(nums1.size()) || j < static_cast(nums2.size())) {
if (j == static_cast(nums2.size()) || (i < static_cast(nums1.size()) && nums1[i] <= nums2[j])) {
merged.push_back(nums1[i++]);
} else {
merged.push_back(nums2[j++]);
}
}
const int total = static_cast(merged.size());
const int middle = total / 2;
if (total % 2 == 1) {
return merged[middle];
}
return (static_cast(merged[middle - 1]) + static_cast(merged[middle])) / 2.0;
}
double walkToMiddle(const std::vector& nums1, const std::vector& nums2) {
const int total = static_cast(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(nums2.size()) || (i < static_cast(nums1.size()) && nums1[i] <= nums2[j])) {
current = nums1[i++];
} else {
current = nums2[j++];
}
}
if (total % 2 == 1) {
return current;
}
return (static_cast(previous) + static_cast(current)) / 2.0;
}
double binaryPartition(const std::vector& nums1, const std::vector& nums2) {
if (nums1.size() > nums2.size()) {
return binaryPartition(nums2, nums1);
}
const int m = static_cast(nums1.size());
const int n = static_cast(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::lowest() : nums1[cut1 - 1];
const long long right1 = cut1 == m ? std::numeric_limits::max() : nums1[cut1];
const long long left2 = cut2 == 0 ? std::numeric_limits::lowest() : nums2[cut2 - 1];
const long long right2 = cut2 == n ? std::numeric_limits::max() : nums2[cut2];
if (left1 <= right2 && left2 <= right1) {
const long long leftMax = std::max(left1, left2);
if ((m + n) % 2 == 1) {
return static_cast(leftMax);
}
const long long rightMin = std::min(right1, right2);
return (static_cast(leftMax) + static_cast(rightMin)) / 2.0;
}
if (left1 > right2) {
high = cut1 - 1;
} else {
low = cut1 + 1;
}
}
return 0.0;
}
public:
double findMedianSortedArrays(std::vector& nums1, std::vector& 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``:
.. code-block:: text
nums1: 左侧 cut1 个元素 | 右侧剩余元素
nums2: 左侧 cut2 个元素 | 右侧剩余元素
令合并后左侧元素数量为 ``leftSize = (m + n + 1) / 2``,于是 ``cut2 = leftSize - cut1``。只要搜索 ``cut1``,另一条分割线就被唯一确定。
公式中的 ``+1`` 统一了奇偶情况:总长度为偶数时左右数量相同;总长度为奇数时左侧比右侧多一个元素,中位数就落在左侧最大值上。
合法分割
~~~~~~~~
每个数组内部已经有序,所以只需观察分割线附近四个值:
.. code-block:: text
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``:
.. list-table::
:header-rows: 1
* - 轮次
- ``cut1``
- ``cut2``
- 左边界
- 右边界
- 处理
* - 1
- 1
- 3
- ``left1 = 1, left2 = 5``
- ``right1 = 2, right2 = 6``
- ``left2 > right1``,右移 ``cut1``
* - 2
- 2
- 2
- ``left1 = 2, left2 = 4``
- ``right1 = 8, right2 = 5``
- 合法分割
合法分割的左侧包含 ``[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)`` 工作空间。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 主要代价
* - 完整归并
- ``O(m + n)``
- ``O(m + n)``
- 生成并保存全部合并元素
* - 中位截断
- ``O(m + n)``
- ``O(1)``
- 逐个生成前半部分元素
* - 二分分割
- ``O(log min(m, n))``
- ``O(1)``
- 搜索较短数组中的合法分割位置
边界处理
~~~~~~~~
* 一侧数组为空时,负无穷和正无穷哨兵让分割条件仍然成立;
* 总长度为奇数时,左侧故意多保留一个元素,直接返回左侧最大值;
* 总长度为偶数时,先把两个中间值转换为 ``double`` 再相加,避免整数平均造成截断;
* 数组中存在重复值时,合法条件使用 ``<=``,相等元素可以分布在分割线两侧;
* 主解法只读取输入数组,不修改其内容。