给定两个大小分别为 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
- 示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
- 示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
- 示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
- 提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
暴力解法
思路
合并两个代码后从小到大排序，数组总数是奇数取nums[n/2]，是偶数则取(nums[n/2] + nums[n/2-1]) / 2
代码
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
let n = nums1.length + nums2.length;
let nums = nums1.concat(nums2).sort((a, b) => a - b);
let result =
n % 2 == 0 ? (nums[n / 2] + nums[n / 2 - 1]) / 2 : nums[Math.floor(n / 2)];
return result;
};
复杂度
- 时间复杂度 O(NlogN)，N为两数组的长度和
- 空间复杂度 O(N)
双指针法
思路
因为两个数组有序，求中位数不需要把两个数组合并
当合并后的数组总长度len为奇数时，只要知道索引为len/2位置上的数就行了，如果数偶数，只要知道索引为len/2 - 1和len/2上的数就行，所以不管是奇数还是偶数只要遍历len/2次即可，用两个值来存遍历过程中len/2-1和len/2上的数即可
两个指针point1和point2分别指向nums1和nums2，当nums1[point1] < nums2[point2]，则point1指针移动，否则point2指针移动
代码
/**
*
*
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
let n1 = nums1.length;
let n2 = nums2.length;
// 两个数组总长度
let len = n1 + n2;
// 保存当前移动的指针的值(在nums1或nums2移动)，和上一个值
let preValue = -1;
let curValue = -1;
// 两个指针分别在nums1和nums2上移动
let point1 = 0;
let point2 = 0;
// 需要遍历len/2次，当len是奇数时，最后取curValue的值，是偶数时，最后取(preValue + curValue)/2的值
for (let i = 0; i <= Math.floor(len / 2); i++) {
preValue = curValue;
// 需要在nums1上移动point1指针
if (point1 < n1 && (point2 >= n2 || nums1[point1] < nums2[point2])) {
curValue = nums1[point1];
point1++;
} else {
curValue = nums2[point2];
point2++;
}
}
return len % 2 === 0 ? (preValue + curValue) / 2 : curValue;
};
复杂度
- 时间复杂度O(n+m)，n为nums1的长度，m为nums2的长度
- 空间复杂度O(1)
二分查找
思路
对于中位数的简单分析
如果两个数组长度和为奇数，那么最终这个中位数是由一位数确定的。
如果两个数组长度和为偶数，那么最终这个中位数是由两位数取平均值确定的。
对两个数组的简单分析：
两个数组应该有一个长一点，另一个点一点(等长也不影响)。
中位数可能让两个数组都分成两部分：一部分小于中位数，一部分大于中位数。但两个部分合起来总数量应该一致。
对两数组和中位数位置分析：
我们知道两数组虽然可能等长(不影响)，但正常情况应该是一个长(m)一个短(n)。长短数组分别对应的坐标m1和n1和中位数坐标有什么关系？
无论总和奇数偶数，都满足(m1+n1)=(m+n)/2;因为两个数组都是有序的所以总共小于中位数的占一半。其中m和n是定值。也就是不管你怎么变动，这两个坐标编号总和为定值。
如何分析为定值得坐标
既然两个坐标的总和为定值，那么可不可以把其中一个当为自变量，一个看成自变量呢？
比如x+y=5你不好分析但是y=5-x，你分析x同时y就确定了。对吧？
那么选择长的那个作为变量还是短的那个作为变量呢？短的。
为啥？主要因为如果从长的当成变量咱们有些区域无法对应到短的(因为长度即使加上短的所有也到不了一半，处理起来麻烦，但是短的就可以很好避免这种情况。
所以我们就用二分去查找小的这个区间，找到最终的结果，你可能会问：什么样情况能够满足确定这条线的附近就是产生中位数的？
二分进行查找编号的时候，满足左侧都比线右侧小才行。这种情况在二分查找就是一个平衡的结果。
最后找到这个index线了。取值比较你还要有注意的地方：取左侧的时候左侧如果有index为0，取右侧的时候index为最大值。
所以在最后取值的时候，需要考虑左右侧是否有值。同时取长的那个也要比较，因为可能出现等长情况例如：1 2 3 4,和5 6 7 8这种去到临界。需要判断当然在实现过程用三目运算简化！
总结：
- 根据短的进行二分查找位置，先找到线index，说明中位数在附近产生。（奇数偶数在查找因为要除2可以通用表达式）
- 如果总个数奇数，那么就是线左侧最大的那个(两个比较或只有一个)
- 如果总个数偶数，那么就是线左侧最大的那个(两个比较或只有一个)和线右侧最小的那个(两个比较或只有一个)的值取平均，注意是double类型。
- 其他注意点，搞清index从0开始，搞清逻辑上的第几个和数组显示使用的第几个的index的区别。
代码
/**
*
*
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
// nums1长度比nums2小
if (nums1.length > nums2.length) {
[nums1, nums2] = [nums2, nums1];
}
let m = nums1.length;
let n = nums2.length;
// 在0～m中查找
let left = 0;
let right = m;
// median1：前一部分的最大值
// median2：后一部分的最小值
let median1 = 0;
let median2 = 0;
while (left <= right) {
// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
const i = left + Math.floor((right - left) / 2);
const j = Math.floor((m + n + 1) / 2) - i;
const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
const minRight1 = i === m ? Infinity : nums1[i];
const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
const minRight2 = j === n ? Infinity : nums2[j];
if (maxLeft1 <= minRight2) {
median1 = Math.max(maxLeft1, maxLeft2);
median2 = Math.min(minRight1, minRight2);
left = i + 1;
} else {
right = i - 1;
}
}
return (m + n) % 2 == 0 ? (median1 + median2) / 2 : median1;
};
复杂度
- 时间复杂度O(log(min(m, n)))，n为nums1的长度，m为nums2的长度
- 空间复杂度O(1)