学习记录：js算法（四十二）：寻找两个正序数组的中位数

文章目录

- 寻找两个正序数组的中位数
- - 我的思路
  - 网上思路
- 总结

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

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

示例 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

我的思路
排序，然后根据长度进行判断；想使用二分法，但是没找到二分法的判断条件，卡壳了。
网上思路
二分法

我的思路

var findMedianSortedArrays = function (nums1, nums2) {
    let arr = [...nums1, ...nums2].sort((a, b) => a - b)
    let len = arr.length
    return len % 2 === 0 ? (arr[len / 2] + arr[len / 2 - 1]) / 2 : arr[(len - 1) / 2]
};

讲解

合并数组并排序
取余判断
如果无余数，那么下标就是 arr.length / 2 和 arr.length / 2 - 1
有余数，那么下标就是 (arr.length - 1) / 2

网上思路

/**
 * 二分解法
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
  // make sure to do binary search for shorten array
  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 = low + 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]

    if (maxLeftA <= minRightB && minRightA >= maxLeftB) {
      return (m + n) % 2 === 1
        ? Math.max(maxLeftA, maxLeftB)
        : (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2
    } else if (maxLeftA > minRightB) {
      high = i - 1
    } else {
      low = low + 1
    }
  }
};

讲解
由于题中给出的数组都是排好序的，在排好序的数组中查找很容易想到可以用二分查找, 这里对数组长度小的做二分，
保证数组A 和 数组B 做partition 之后
len(Aleft)+len(Bleft)=(m+n+1)/2 - m 是 数组A 的长度， n 是 数组B 的长度
对 数组A 的做 partition 的位置是区间 [0,m]
如图：

下图给出几种不同情况的例子（注意但左边或者右边没有元素的时候，左边用INF_MIN，右边用INF_MAX表示左右的元素：

下图给出具体做的partition 解题的例子步骤，

关键点分析
暴力求解，在线性时间内 merge 两个排好序的数组成一个数组。
二分查找，关键点在于
要 partition 两个排好序的数组成左右两等份，partition 需要满足 len(Aleft)+len(Bleft)=(m+n+1)/2 - m 是 数组A 的长度， n 是 数组B 的长度
并且 partition 后 A 左边最大 (maxLeftA), A 右边最小 (minRightA) , B 左边最大 (maxLeftB) , B 右边最小 (minRightB) 满足
(maxLeftA <= minRightB && maxLeftB <= minRightA)
有了这两个条件，那么 median 就在这四个数中，根据奇数或者是偶数，
// 奇数：
median = max(maxLeftA, maxLeftB)
// 偶数：
median = (max(maxLeftA, maxLeftB) + min(minRightA, minRightB)) / 2
作者：lucifer
链接：点击跳转