HHot 100C++ 图解

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 == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= 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)。

图解

1 0 2 1 3 2 4 3 5 4
数组(来自本仓库测试数据,下标从 0 开始)

C++17 题解

src/11_binary_search.cpp28 行
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;  // 输入保证有序,理论到不了这里
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q4_median_of_two_sorted_arrays16 行
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);

↑↓ 选择↵ 打开/ 随时唤起