原题地址：寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5
暴力解法
中位数（又称中值，英语：Median），统计学中的专有名词，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。
对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。
不考虑时间复杂度的要求，我们就可以将两个数组合并然后排序，这时候中间位置的数即为中位数：
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
const findMedianSortedArrays1 = function(nums1, nums2) {
let array = new Array(nums1.length + nums2.length);
let [i, j] = [0, 0];
// 由于两个子数组已经有序，采用归并排序是最快的
while (i < nums1.length && j < nums2.length) {
if (nums1[i] < nums2[j]) {
array[i + j] = nums1[i];
i ++;
} else {
array[i + j] = nums2[j];
j ++;
}
}
while (i < nums1.length) {
array[i + nums2.length] = nums1[i];
i ++;
}
while (j < nums2.length) {
array[nums1.length + j] = nums2[j];
j ++;
}
// 此时i = nums1.length, j = nums2.length
if ((i + j) % 2 === 0) { // 长度为偶数时，取最中间两个数的平均数
return (array[(i + j) / 2 - 1] + array[(i + j) / 2]) / 2;
} else { // 否则取正中间位置的数
return array[(i + j - 1) / 2];
}
};
测试
let start = new Date();
const test = findMedianSortedArrays1;
console.log(test([1, 3], [2])); // 2
console.log(test([1, 2], [3, 4])); // 2.5
console.log(new Date().getTime() - start.getTime()); // 8
时间复杂度： 排序时需要遍历两个数组，时间复杂度为O(m+n)，不符合题目要求
空间复杂度： 新数组的长度为两个数组的长度之和，空间复杂度为O(m+n)
暴力解法的优化
题目要求的是寻找中位数，所以我们并不一定要将两个数组合并，只要能找到一个或者两个数，两个数组中比它们大的和小的数量一样多就可以了。
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 27,2019