4. 寻找两个正序数组的中位数
一句话套路只在短数组上枚举合法切点
题目描述
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1:
输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2
示例 2:
输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
提示:
nums1.length == mnums2.length == n0 <= m <= 10000 <= n <= 10001 <= m + n <= 2000-106 <= nums1[i], nums2[i] <= 106
思路
时间O(log(min(m,n)))
空间
O(1)思路(划分数法)
中位数把两个数组各自切成「左半 / 右半」,要求
- ① 左半元素总数 = 右半(或比右半多 1)
- ② A 的左最大 <= B 的右最小,且 B 的左最大 <= A 的右最小
只在较短数组上枚举切点 i(保证 O(log(min(m,n)))),j 由 ① 直接算出。
边界用 ±INF 表示「这一侧没有元素」,可以把四种情况统一成一行 max/min。
备用解法
求「第 k 小」,每次扔掉两个数组各 k/2 个 -> O(log(m+n)),更好想。
别用
合并后取中位是 O(m+n),不满足题目要求(虽然能 AC)。
图解
数组(来自本仓库测试数据,下标从 0 开始)
C++17 题解
namespace lc0004 {
class Solution {
public:
double findMedianSortedArrays(vector<int>& a, vector<int>& b) {
if (a.size() > b.size()) return findMedianSortedArrays(b, a); // 让 a 更短
const int m = (int)a.size(), n = (int)b.size();
const int half = (m + n + 1) / 2; // 左半元素总数(奇数时归左半)
int lo = 0, hi = m;
while (lo <= hi) {
int i = lo + (hi - lo) / 2; // a 贡献 i 个到左半
int j = half - i; // b 贡献剩下的
int aL = (i == 0) ? INT_MIN : a[i - 1];
int aR = (i == m) ? INT_MAX : a[i];
int bL = (j == 0) ? INT_MIN : b[j - 1];
int bR = (j == n) ? INT_MAX : b[j];
if (aL <= bR && bL <= aR) { // 切法合法
if ((m + n) % 2 == 1) return std::max(aL, bL);
return (static_cast<double>(std::max(aL, bL)) + std::min(aR, bR)) / 2.0;
}
if (aL > bR)
hi = i - 1; // a 取多了
else
lo = i + 1; // a 取少了
}
return 0.0; // 输入保证有序,理论到不了这里
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0004::Solution s;
vector<int> a1{1, 3}, b1{2};
CHECK_NEAR(s.findMedianSortedArrays(a1, b1), 2.0, 1e-9);
vector<int> a2{1, 2}, b2{3, 4};
CHECK_NEAR(s.findMedianSortedArrays(a2, b2), 2.5, 1e-9);
vector<int> a3{}, b3{1};
CHECK_NEAR(s.findMedianSortedArrays(a3, b3), 1.0, 1e-9); // 一个数组为空
vector<int> a4{2}, b4{};
CHECK_NEAR(s.findMedianSortedArrays(a4, b4), 2.0, 1e-9);
vector<int> a5{1, 2, 3, 4, 5}, b5{6, 7, 8};
CHECK_NEAR(s.findMedianSortedArrays(a5, b5), 4.5, 1e-9);
vector<int> a6{1, 1}, b6{1, 1}; // 全相等
CHECK_NEAR(s.findMedianSortedArrays(a6, b6), 1.0, 1e-9);
vector<int> a7{-5, 3, 6, 12, 15}, b7{-12, -10, -6, -3, 4, 10};
// 合起来排序后共 11 个,中位数是第 6 个 = 3
CHECK_NEAR(s.findMedianSortedArrays(a7, b7), 3.0, 1e-9);