两个正序数组的中位数

描述

给定两个大小为 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

示例3

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例4

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例5

输入：nums1 = [2], nums2 = []
输出：2.00000

条件

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */

方法

1. 暴力法

比较好理解，就是合并数组，然后sort排序。
按题目要求，合并的数组长度是奇数时找出中间数，偶数时找出中间两个数并求平均数。
代码如下

var findMedianSortedArrays = function(nums1, nums2) {
  let allNums = nums1.concat(nums2)
  let sortAllNums = allNums.sort((a, b) => a - b) // 排序后的
  if (sortAllNums.length % 2) { // 奇数
    return sortAllNums[(sortAllNums.length - 1) / 2]
  } else { // 偶数
    return (sortAllNums[sortAllNums.length / 2] + sortAllNums[sortAllNums.length / 2 - 1]) / 2
  }

2. 二分法

本文主要讲二分法，因为题目的进阶要求是时间复杂度为 O(log (m+n))。这种时间复杂度有对数的时候，一般都要想到用二分法来处理这个问题。

首先，我们规定数组A的长度为m，数组B的长度为n，且m <= n。这里我们以小的数组做2分。

对于A数组，以l代表分割线位置,分割线左范围值l0 = 0置，分割线右范围值li = m。那么分割线位置i应该是 (l0 + li) / 2

那么数组A以 i 作二分，数组B以 j 作二分。那么根据题目的要求，i + j 要满足等于 (m + n + 1) / 2 (编程语言向下取整)。

20201107213428.jpg

那么所得的分各项两边的数需要满足如下条件：

1. Ai < Bj+1

2. Bj < Ai+1

满足上述条件，再根据m + n的奇偶性求出中位数。

如果不满足上述条件，说明分割线的位置错误。需要重新利用二分法二分剩下的位置，去寻找合适的分割线。

如果Ai > Bj+1 A数组分割线左边大了，说明分割线太靠右了，需要向左移动。将分割线右范围值在目前分割线的基础上向左移动一位。li = i - 1。

如果Bj > Ai+1 A数组右边小了，说明分割线太靠左了，需要向右移动，将分割线左范围在原来基础上向右移动一位。l0 = i + 1。

那么 i = (l0 + li) / 2; j = (m + n + 1) - i。

推理过程如下图:

过程图
过程图

代码

const findMedianSortedArrays  = (nums1, nums2) => {
  // 确保第一个数组长度较小
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1]
  }

  const m = nums1.length
  const n = nums2.length
  let low = 0
  let high = m

  while (low <= high) {
    const i = Math.floor((high + low) / 2)
    const j = Math.floor((m + n + 1) / 2) - i

    const maxLeftA = i === 0 ? -Infinity : nums1[i - 1]
    const minRightA = i === m ? Infinity : nums1[i]
    const maxLeftB = j === 0 ? -Infinity : nums2[j - 1]
    const minRightB = j === n ? Infinity : nums2[j]

    // 判断上面4个数的关系
    if (maxLeftA <= minRightB && minRightA >= maxLeftB) { // 满足条件
      // 判断奇偶性 然后得出结果
      return (m + n) % 2 === 1 ? Math.max(maxLeftA, maxLeftB) : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2
    }
    if (maxLeftA > minRightB) { // 分割线需要左移动
      high = i - 1
    }
    if (minRightA < maxLeftB) { // 分割线需要右移动
      low = i + 1
    }
  }
}

本文参考资料为leetCode的清华大佬lucifer