Open sisterAn opened 3 years ago
const findMedianSortedArrays = (nums1, nums2) => {
if (!nums1.length && !nums2.length) {
return null;
}
// 如果数组1为空
if (!nums1.length) {
// 若此时数组2仅一个值,那么该值为中位数
if (nums2.length === 1) {
return nums2[0];
}
/**
* 否则比较数组2,取中位数
* 比较单个数组采用二分法
*/
let half = Math.floor(nums2.length / 2);
return findMedianSortedArrays(nums2.slice(0, half), nums2.slice(half));
}
// 如果数组2为空,同理
if (!nums2.length) {
if (nums1.length === 1) {
return nums1[0];
}
let half = Math.floor(nums1.length / 2);
return findMedianSortedArrays(nums1.slice(0, half), nums1.slice(half));
}
// 如果两个数组都只剩1个数,取两者中间值
if (nums1.length === 1 && nums2.length === 1) {
return nums1[0] === nums2[0] ? nums1[0] : (nums1[0] + nums2[0]) / 2;
}
// 比较两个数组的最小值,丢弃最小值
nums1[0] < nums2[0] ? nums1.shift() : nums2.shift();
/**
* 这里注意边界值,丢弃最小值后有的数组可能为空
*/
if (!nums1.length) {
// 强制丢掉最大值
nums2.pop();
return findMedianSortedArrays(nums1, nums2);
}
if (!nums2.length) {
nums1.pop();
return findMedianSortedArrays(nums1, nums2);
}
// 比较两个数组的最大值,丢弃最大值
nums1[nums1.length - 1] > nums2[nums2.length - 1] ? nums1.pop() : nums2.pop();
// 重复该操作
return findMedianSortedArrays(nums1, nums2);
};
思路:比较两个有序数组的最小值与最大值,剔除最大最小值后重新比较 重复此操作,直到剩余1个数,那么该数为中位数 如果剩余2个数,那么中位数为两者和除2 单数组采用二分法
注意:边界值比较多
该题耗时:20ms(击败了99%),内存消耗:41.9M(击败了94%)
来个简单点的:
const arr1 = [1, 2, 10];
const arr2 = [2, 5, 7, 8];
function findMiddleNumber(arr1, arr2) {
// 容错处理
if (!arr1.length && !arr2.length) return null;
// 合并并排序
const total = [...arr1, ...arr2].sort((a, b) => a - b);
// 中位数索引
let midIndex = (total.length - 1) / 2;
// 两位
if (String(midIndex).includes(".")) {
const left = parseInt(midIndex);
const right = parseInt(midIndex) + 1;
const midNumber = (total[left] + total[right]) / 2;
return midNumber.toFixed(5);
} else {
// 一位
return total[midIndex].toFixed(5);
}
}
console.log(findMiddleNumber(arr1, arr2));
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 1:
示例 2:
示例 3:
示例 4:
示例 5:
提示:
进阶:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗?
leetcode