两个正序数组的中位数
描述
给定两个大小为 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 (编程语言向下取整)。
那么所得的分各项两边的数需要满足如下条件：
Ai < Bj+1
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
}
}
}
