用JS实现给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
时间: 2024-02-19 07:02:31 浏览: 28
好的,这是一道很经典的算法题,需要用到二分查找和数组操作。以下是实现代码:
```javascript
function findMedianSortedArrays(nums1, nums2) {
const m = nums1.length;
const n = nums2.length;
if (m > n) {
return findMedianSortedArrays(nums2, nums1);
}
let left = 0;
let right = m;
while (left <= right) {
const i = Math.floor((left + right) / 2);
const j = Math.floor((m + n + 1) / 2) - i;
const maxLeftA = i === 0 ? -Infinity : nums1[i - 1];
const minRightA = i === m ? Infinity : nums1[i];
const maxLeftB = j === 0 ? -Infinity : nums2[j - 1];
const minRightB = j === n ? Infinity : nums2[j];
if (maxLeftA <= minRightB && maxLeftB <= minRightA) {
if ((m + n) % 2 === 0) {
return (Math.max(maxLeftA, maxLeftB) + Math.min(minRightA, minRightB)) / 2;
} else {
return Math.max(maxLeftA, maxLeftB);
}
} else if (maxLeftA > minRightB) {
right = i - 1;
} else {
left = i + 1;
}
}
}
```
这个函数的时间复杂度是 $O(log(min(m, n)))$,因为每次都能将搜索范围减半。