题目描述
给定两个大小为 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
中位数
对于一组有限个数的数据来说，其中位数是这样的一种数：这群数据的一半的数据比它大，而另外一半数据比它小。
计算有限个数的数据的中位数的方法是：把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数，则中间那个数据就是这群数据的中位数；如果数据的个数是偶数，则中间那2个数据的算术平均值就是这群数据的中位数。
解法
解法一
原理： 将两数组将加，然后进行排序，取中位数。
在不考虑时间复杂度的情况下的解法：
var findMedianSortedArrays = function(nums1, nums2) {
const arr = nums1.concat(nums2);
arr.sort((a, b) => a-b);
const len = arr.length;
if (len%2 === 1) {
const result = arr[Math.floor(len/2)];
return result.toFixed(2);
}
if (len%2 === 0) {
const result = (arr[Math.floor(len/2)] + arr[Math.floor(len/2 -1)])/2;
return result.toFixed(2);
}
};
解法二
假设有两个有序数组A（m个元素）、B（n个元素）。
中位数切分
var findMedianSortedArrays = function(A, B) {
let m = A.length;
let n = B.length;
// 为了保证 m <= n
if (m > n) {
const temp = A;
A = B;
B = temp;
const temp_len = m;
m = n;
n = temp_len;
}
let i_min = 0, i_max = m, half_len = (m + n + 1) / 2;
while (i_min <= i_max) {
const i = Math.floor((i_min + i_max) / 2);
const j = Math.floor(half_len - i);
// B[j - 1] > A[j], i 太小需要调大
if (i < i_max && B[j - 1] > A[i]) {
i_min = i + 1;
} else if (i > i_min && A[i-1] > B[j]) {
i_max = i - 1;
} else {
// 获取左边最大值
let max_left = 0;
// 当 i=0时，表示集合A左边无数据，则左边最大为 B[j-1]
if (i == 0) {
max_left = B[j - 1];
} else if (j == 0) {
max_left = A[i - 1];
} else {
max_left = Math.max(A[i - 1], B[j - 1]);
}
// 若 m + n 为奇数
if ((m + n) % 2 == 1) {
return max_left;
}
let min_right = 0;
if (i == m) {
min_right = B[j];
} else if (j == n) {
min_right = A[i];
} else {
min_right = Math.min(B[j], A[i]);
}
return ((max_left + min_right) / 2).toFixed(2);
}
}
return 0.0;
};
