#4. 寻找两个正序数组的中位数

LeetCode 原题链接

#1. 题目描述

给定两个正序数组 nums1 和 nums2，要求找出这两个数组合并后的中位数。

注意题目要求整体时间复杂度为 O(log(m + n))，所以不能真的把两个数组完整合并后再取中位数。

示例 1：

输入：nums1 = [1, 3], nums2 = [2]
输出：2
解释：合并后数组为 [1, 2, 3]，中位数是 2。

示例 2：

输入：nums1 = [1, 2], nums2 = [3, 4]
输出：2.5
解释：合并后数组为 [1, 2, 3, 4]，中位数是 (2 + 3) / 2 = 2.5。

#2. 题型判断

本题给出的两个数组都已经有序，并且要求 O(log(m + n))，所以优先考虑二分法。

普通合并两个有序数组需要 O(m + n)，不满足题目要求。真正要找的是中位数，也就是把两个数组切成左右两部分：

• 左半部分元素数量等于右半部分，或者比右半部分多 1 个。
• 左半部分的所有元素都小于等于右半部分的所有元素。

只要找到这样的切分位置，就能直接计算中位数。

#3. 核心思路

在较短的数组上做二分，选择 nums1 的切分位置 i，然后根据总左半部分数量反推出 nums2 的切分位置 j。

假设：

leftSize = Math.floor((m + n + 1) / 2)

那么要保证：

i + j = leftSize

切分后：

nums1: [0 ... i - 1] | [i ... m - 1]
nums2: [0 ... j - 1] | [j ... n - 1]

要让左半部分都小于等于右半部分，只需要检查边界上的 4 个值：

nums1Left <= nums2Right
nums2Left <= nums1Right

这 4 个值分别表示：

nums1Left  = nums1 左半部分的最大值
nums1Right = nums1 右半部分的最小值
nums2Left  = nums2 左半部分的最大值
nums2Right = nums2 右半部分的最小值

因为 nums1 和 nums2 本身都是有序数组，所以：

nums1 左半部分 <= nums1 右半部分
nums2 左半部分 <= nums2 右半部分

这两个关系天然成立。真正需要额外检查的是两个数组之间的交叉关系：

nums1 左边最大值 是否 <= nums2 右边最小值
nums2 左边最大值 是否 <= nums1 右边最小值

如果这两个条件都满足，说明切分合法。

如果 nums1Left > nums2Right，说明 nums1 左边取多了，i 要向左移动。

如果 nums2Left > nums1Right，说明 nums1 左边取少了，i 要向右移动。

#4. 示例步骤图解

以：

nums1 = [1, 3, 8]
nums2 = [2, 7, 10, 11]

为例。nums1 长度是 3，nums2 长度是 4，已经满足在较短数组上二分，所以不需要交换。

总长度是 7，左半部分需要：

leftSize = Math.floor((3 + 4 + 1) / 2) = 4

也就是说，我们要把两个数组切成：

左半部分一共 4 个元素
右半部分一共 3 个元素

二分过程：

合法切分为：

nums1: [1, 3] | [8]
nums2: [2, 7] | [10, 11]

左半部分：[1, 3, 2, 7]
右半部分：[8, 10, 11]

此时 4 个边界值分别是：

nums1Left  = 3
nums1Right = 8
nums2Left  = 7
nums2Right = 10

所以两个交叉条件是：

nums1Left <= nums2Right  =>  3 <= 10
nums2Left <= nums1Right  =>  7 <= 8

这两个条件都成立，说明左半部分所有元素都小于等于右半部分所有元素。

左半部分最大值是 7，右半部分最小值是 8，满足：

7 <= 8

总长度是奇数，所以中位数就是左半部分最大值：

max(3, 7) = 7

#5. 变量与区间含义

• m：较短数组 nums1 的长度。
• n：较长数组 nums2 的长度。
• leftSize：合并后左半部分应该包含的元素数量。
• left、right：在 nums1 上二分切分位置 i 的范围，使用闭区间 [left, right]。
• i：nums1 的切分位置，左边有 i 个元素。
• j：nums2 的切分位置，左边有 j 个元素，且 j = leftSize - i。
• nums1Left：nums1 左半部分最大值。
• nums1Right：nums1 右半部分最小值。
• nums2Left：nums2 左半部分最大值。
• nums2Right：nums2 右半部分最小值。

边界处理：

• 如果 i === 0，说明 nums1 左半部分为空，nums1Left = -Infinity。
• 如果 i === m，说明 nums1 右半部分为空，nums1Right = Infinity。
• nums2 同理。

#6. 推进规则

每次二分得到 i 后，计算：

j = leftSize - i

然后比较边界：

• 如果 nums1Left <= nums2Right 且 nums2Left <= nums1Right，说明切分合法。
• 如果 nums1Left > nums2Right，说明 nums1 左边元素太大，也就是 i 太大，需要 right = i - 1。
• 如果 nums2Left > nums1Right，说明 nums1 左边元素太少，也就是 i 太小，需要 left = i + 1。

找到合法切分后：

• 如果总长度是奇数，中位数是 Math.max(nums1Left, nums2Left)。
• 如果总长度是偶数，中位数是 (Math.max(nums1Left, nums2Left) + Math.min(nums1Right, nums2Right)) / 2。

#7. 边界条件与易错点

• 必须在较短数组上二分，才能保证 j 不会越界。
• 切分位置 i 的范围是 [0, m]，不是数组下标范围 [0, m - 1]。
• i 和 j 表示左半部分元素个数，不是具体元素下标。
• 空半边要用 -Infinity 或 Infinity 处理，否则边界判断会很麻烦。
• leftSize 要写成 Math.floor((m + n + 1) / 2)，这样总长度为奇数时，左半部分会多一个元素，方便直接取左半部分最大值。
• 如果 nums1 比 nums2 长，要先交换两个数组。

#8. 代码实现

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  // 始终在较短数组 nums1 上二分。
  // 因为 i 是 nums1 的切分位置，j = leftSize - i 是 nums2 的切分位置。
  // 如果在较长数组上二分，i 可能过大或过小，导致 j < 0 或 j > nums2.length。
  // 先交换数组，可以让 i 的搜索范围更小，从而更容易保证 j 落在 nums2 的合法切分范围内。
  if (nums1.length > nums2.length) {
    return findMedianSortedArrays(nums2, nums1);
  }

  const m = nums1.length;
  const n = nums2.length;

  // 左半部分需要包含的元素数量。
  // 总长度为奇数时，左半部分比右半部分多一个元素。
  const leftSize = Math.floor((m + n + 1) / 2);

  // i 是 nums1 的切分位置，范围是 [0, m]。
  let left = 0;
  let right = m;

  while (left <= right) {
    const i = left + Math.floor((right - left) / 2);
    const j = leftSize - i;

    // i 或 j 位于边界时，用无穷值表示空半边。
    const nums1Left = i === 0 ? -Infinity : nums1[i - 1];
    const nums1Right = i === m ? Infinity : nums1[i];
    const nums2Left = j === 0 ? -Infinity : nums2[j - 1];
    const nums2Right = j === n ? Infinity : nums2[j];

    if (nums1Left <= nums2Right && nums2Left <= nums1Right) {
      // 找到合法切分：左半部分所有元素都 <= 右半部分所有元素。
      const leftMax = Math.max(nums1Left, nums2Left);
      const rightMin = Math.min(nums1Right, nums2Right);

      if ((m + n) % 2 === 1) {
        return leftMax;
      }

      return (leftMax + rightMin) / 2;
    } else if (nums1Left > nums2Right) {
      // nums1 左边取多了，切分位置 i 需要左移。
      right = i - 1;
    } else {
      // nums1 左边取少了，切分位置 i 需要右移。
      left = i + 1;
    }
  }
};

#9. 复杂度分析

• 时间复杂度：O(log(min(m, n)))。因为只在较短数组上二分。
• 空间复杂度：O(1)。只使用了常数个变量。