4. Median of Two Sorted Arrays
source: https://leetcode.com/problems/median-of-two-sorted-arrays/
Question
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
初想法
如果使用已有的sort函数，看v8的代码：
在数组长度小于等于10时是用插入排序，大于10是用快速排序。
这里我们先只考虑快速排序，那么平均状况下时间复杂度是O(nlogn)，和题目要求的O(logn)相比还是有差距的。
var findMedianSortedArrays = function (nums1, nums2) {
const arr = [...nums1, ...nums2].sort((a, b) => a - b);
return arr.length % 2 === 1
? arr[(arr.length - 1) / 2]
: (arr[Math.floor((arr.length - 1) / 2)] +
arr[Math.ceil((arr.length - 1) / 2)]) /
2;
};
二分查找
这里有一个很重要的前提条件，这两个数组是sorted的。
在此前提下，每次找k/2个元素，根据两个数组k/2位置元素的大小，就可以排除k/2个元素，然后一步步找到第k个元素。
时间复杂度是O(log(m+n)).
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function (nums1, nums2) {
/**
* 找到两个sorted arrays的排序为k的元素
*/
const getKthElement = (k) => {
const len1 = nums1.length;
const len2 = nums2.length;
let index1 = 0;
let index2 = 0;
while (true) {
if (index1 === len1) {
// * nums1 到头了
return nums2[index2 + k - 1];
} else if (index2 === len2) {
// * nums2 到头了
return nums1[index1 + k - 1];
} else if (k === 1) {
// * 最后一次比较
return Math.min(nums1[index1], nums2[index2]);
}
const half = k >> 1; // JS 中 k/2 不是整除，可以用parseInt(k/2)代替
let newIndex1 = Math.min(index1 + half - 1, len1 - 1); // * 要注意index1+half-1可能会越界溢出, 所以下标最大为len1-1
let newIndex2 = Math.min(index2 + half - 1, len2 - 1); // 同上
if (nums1[newIndex1] <= nums2[newIndex2]) {
// * 开始抛弃部分序列，更新K值，抛弃的长度为newIndex1 - index1 + 1，对应end-start+1
k -= newIndex1 - index1 + 1;
index1 = newIndex1 + 1; // * 更新抛弃过的序列的下标
} else {
// 同上
k -= newIndex2 - index2 + 1;
index2 = newIndex2 + 1;
}
}
};
const totalLength = nums1.length + nums2.length;
const median = totalLength >> 1;
// * 核心思路为, 用二分找到从小到大第K个数
if (totalLength % 2 === 1) {
return getKthElement(median + 1);
} else {
return (getKthElement(median) + getKthElement(median + 1)) / 2;
}
};
End
O(logn)的复杂度可以优先想到二分查找。