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

题目

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

例

输入：nums1 = [1,2], nums2 = [3,4]

输出：2.50000

解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

要求时间复杂度为 O(log (m+n))

题解

最直观的思路有以下两种：

• 使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。
• 不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 00 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

第一种思路的时间复杂度是 O(m+n)，空间复杂度是 O(m+n)。第二种思路虽然可以将空间复杂度降到 O(1)，但是时间复杂度仍是 O(m+n)。题目要求时间复杂度是 O(log(m+n))，因此上述两种思路都不满足题目要求的时间复杂度。

如果对时间复杂度的要求有 log，通常都需要用到二分查找，这道题也可以通过二分查找实现。

二分查找

两个有序数组分别为 A B，要找到第 K 个元素，可以比较 A[k/2-1] B[k/2-1]:

• 如果 A[k/2-1] ≤ B[k/2-1] ，那么比 A[k/2-1] 小的数最多是 k-2 个，所以 A[0] - A[k/2-1] 都不是第 k 个数都可以排除
• 反之如果 A[k/2-1] > B[k/2-1]，则可以排除 B[0] - B[k/2-1]
• 比较完之后排除了 k/2 个，更新 k = k/2

特殊情况：

• A[k/2-1] 或 B[k/2-1] 越界 根据排除数的个数更新 k
• 一个数组为空 直接返回另一个数组中第 k 个元素
• k=1 返回两个数组剩余部分首元素的最小值

点击查看代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  let l1 = nums1.length,
    l2 = nums2.length;

  let totalLen = l1 + l2;

  // 奇数
  if (totalLen % 2) {
    let k = Math.floor(totalLen / 2);
    return getKthEle(nums1, nums2, k + 1);
  } else {
    // 偶数
    let k1 = totalLen / 2 - 1,
      k2 = k1 + 1;
    return (
      (getKthEle(nums1, nums2, k1 + 1) + getKthEle(nums1, nums2, k2 + 1)) / 2
    );
  }
};

// 找到第 k 小的元素
function getKthEle(nums1, nums2, k) {
  let l1 = nums1.length,
    l2 = nums2.length;
  let i1 = (i2 = 0);
  let res = 0;

  while (1) {
    if (i1 == l1) return nums2[i2 + k - 1];
    if (i2 == l2) return nums1[i1 + k - 1];
    if (k == 1) return Math.min(nums1[i1], nums2[i2]);

    let t = Math.floor(k / 2);
    let ii1 = Math.min(i1 + t, l1) - 1;
    let ii2 = Math.min(i2 + t, l2) - 1;

    if (nums1[ii1] <= nums2[ii2]) {
      k -= ii1 - i1 + 1;
      i1 = ii1 + 1;
    } else {
      k -= ii2 - i2 + 1;
      i2 = ii2 + 1;
    }
  }
}

时间复杂度：O(log(m+n)) 其中 m n 是数组 nums1 nums2 的长度，初始 k=(m+n)/2，每轮循环可以将范围减少一般

空间复杂度：O(1)

划分数组

分别将数组 A B 分成左右两个部分 left_A left_B right_A right_B

当 A + B 的总长度是偶数的时候，如果满足：

• len(left_A + left_B) = len(right_A + right_B)
• max(left_A, left_B) ≤ min(right_A, right_B)

那么中位数就是：median = (max(left_A,left_B) + min(right_A, right_B))/2

当 A + B 的总长度是奇数的时候，如果满足：

• len(left_A + left_B) = len(right_A + right_B)+1
• max(left_A, left_B) ≤ min(right_A, right_B)

那么中位数就是：median = max(left_A,left_B)

假设：

• i = len(left_A)
• j = len(left_B)
• m = len(A)
• n = len(B)

第一个条件就是

• m + n 为偶数时 i + j = m - i + n - j
• m + n 为奇数时 i + j = m - i + n - j + 1

可以合并为 i + j = Math.floor((m+n+1)/2) (也就是对结果向下取整)

第二个条件就是 B[j-1] ≤ A[i] && A[i-1] ≤ B[j] j=(m+n+1)/2-i

如果 n<m 可能导致 j 为负数，所以这个时候把数组交换

等价于在 i 在 [0,m] 找到最大的 i 满足 A[i-1] ≤ B[j]

因为如果 i 最大的满足条件说明 i+1 不满足，代入 i+1 到原式得到 B[j-1] < A[i]

点击查看代码

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  let m = nums1.length,
    n = nums2.length;
  if (m > n) return findMedianSortedArrays(nums2, nums1);

  let l = 0,
    r = m;
  let m1 = (m2 = 0);

  while (l <= r) {
    let i = Math.floor((l + r) / 2);
    let j = Math.floor((m + n + 1) / 2) - i;

    let A_im1 = i ? nums1[i - 1] : -Infinity;
    let A_i = i < m ? nums1[i] : Infinity;
    let B_jm1 = j ? nums2[j - 1] : -Infinity;
    let B_j = j < n ? nums2[j] : Infinity;

    if (A_im1 <= B_j) {
      m1 = Math.max(A_im1, B_jm1);
      m2 = Math.min(A_i, B_j);
      l = i + 1;
    } else r = i - 1;
  }

  return (m + n) % 2 ? m1 : (m1 + m2) / 2;
};