寫在前面
此系列來源于開源項目：前端 100 問：能搞懂 80%的請把簡歷給我
為了備戰(zhàn) 2021 春招
每天一題，督促自己
從多方面多角度總結(jié)答案陨帆，豐富知識
給定兩個大小為 m 和 n 的有序數(shù)組 nums1 和 nums2曲秉。請找出這兩個有序數(shù)組的中位數(shù)。要求算法的時間復(fù)雜度為 O(log(m+n))
簡書整合地址：前端 100 問
正文回答
題目
示例 1：
nums1 = [1, 3];
nums2 = [2];
中位數(shù)是 2.0
示例 2：
nums1 = [1, 2];
nums2 = [3, 4];
中位數(shù)是(2 + 3) / 2 = 2.5
回答
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
let m = nums1.length;
let n = nums2.length;
let k1 = Math.floor((m + n + 1) / 2);
let k2 = Math.floor((m + n + 2) / 2);
return (
(findMedianSortedArraysCore(nums1, 0, nums2, 0, k1) +
findMedianSortedArraysCore(nums1, 0, nums2, 0, k2)) /
2
);
};
/**
*
* @param {number[]} nums1
* @param {number[]} nums2
* @param {number} i
* @param {number} j
* @param {number} k
* @return {number}
*/
const findMedianSortedArraysCore = (nums1, i, nums2, j, k) => {
// 如果數(shù)組起始位置已經(jīng)大于數(shù)組長度-1
// 說明已經(jīng)是個空數(shù)組
// 直接從另外一個數(shù)組里取第k個數(shù)即可
if (i > nums1.length - 1) {
return nums2[j + k - 1];
}
if (j > nums2.length - 1) {
return nums1[i + k - 1];
}
// 如果k為1
// 就是取兩個數(shù)組的起始值里的最小值
if (k === 1) {
return Math.min(nums1[i], nums2[j]);
}
// 取k2為(k/2)或者數(shù)組1的長度或者數(shù)組2的長度的最小值
// 這一步可以避免k2大于某個數(shù)組的長度（長度為從起始坐標(biāo)到結(jié)尾）
let k2 = Math.floor(k / 2);
let length1 = nums1.length - i;
let length2 = nums2.length - j;
k2 = Math.min(k2, length1, length2);
let value1 = nums1[i + k2 - 1];
let value2 = nums2[j + k2 - 1];
// 比較兩個數(shù)組的起始坐標(biāo)的值
// 如果value1小于value2
// 就舍棄nums1前i + k2部分
// 否則舍棄nums2前j + k2部分
if (value1 < value2) {
return findMedianSortedArraysCore(nums1, i + k2, nums2, j, k - k2);
} else {
return findMedianSortedArraysCore(nums1, i, nums2, j + k2, k - k2);
}
};
不考慮后半段的題目答案
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
let num = nums1.concat(nums2);
num = num.sort((a, b) => a - b);
let mid = Math.floor(num.length / 2);
if (num.length % 2 === 0) {
return (num[mid - 1] + num[mid]) / 2;
} else {
return num[mid];
}
};
