给定两个大小为 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
这道题是我初学数据算法不久，第一次遇到的困难题。这道题如果没有时间复杂度的限制，则是一道非常简单的题目，但是难点就在这个时间复杂度（很多人都没理解题意，直接拼接了两个数组，然后进行排序直接提交了上去）。当初为了这个时间复杂度，写了100行的算法代码，但却没有通过。实在是有些遗憾。拜读了题解第三的解法，图文并茂。
题解思路是对于两个数组不断的使用二分法进行求解。
第一步操作
比如，有两个数组
[1,3,4,9]
[1,2,3,4,5,6,7,8,9,10]
而两个数组中，我们要求其中位数，则是第 target 为 第 7 位。而同时我们对两个数组进行操作，位数为 7 / 2 向下取整，即同时操作 3 位
则此时
[1,3,4,9]
↑
[1,2,3,4,5,6,7,8,9,10]
↑
由于
4 > 3
我们可以排除掉下边数组包括 3 前边的元素，因为它们必定不是我们要寻找的元素。
现在数组变成了
[1,3,4,9]
[4,5,6,7,8,9,10]
第二步操作
接着在新数组中寻找新的中位数，此时位数由 此时 target 为 7 减去已去除的 3 位，即为 4，按照上面的操作方法，此时我们同时操作 4 / 2 = 2 位
[1,3,4,9]
↑
[4,5,6,7,8,9,10]
↑
由于
5 > 3
我们可以去除上边数组包括 3 前边的元素。
此时数组变为
[4,9]
[4,5,6,7,8,9,10]
第三步操作
第一次操作去除了3位，第二次操作再次去除了 2 位，此时离我们的目标只剩下2位。再次使用上述方法，操作 2 / 2 = 1位
但是此时元素的相等了，那么就假定上边的数组的元素大于下边的数组的元素，进行操作
此时数组变为
[4,9]
[5,6,7,8,9,10]
此时我们还差最后一位进行操作，则直接比较返回即可。
此时代入代码
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var findMedianSortedArrays = function(nums1, nums2) {
//首先获取两个数组的长度，
const length1 = nums1.length
const length2 = nums2.length
const left = parseInt((length1 + length2 + 1) / 2)
const right = parseInt((length1 + length2 + 2) / 2)
//因为总数组的长度的奇偶不同，所需要求的中位数值是不同的，所以我们需要判断一下
if(left === right) {
return getMidNum(nums1, 0, length1 - 1, nums2, 0, length2 - 1, left) //如果左右相同，那么就只用计算一个进行返回
}else {
return (getMidNum(nums1, 0, length1 - 1, nums2, 0, length2 - 1, left) + getMidNum(nums1, 0, length1 - 1, nums2, 0, length2 - 1, right)) / 2//如果左右不能等，那么说明需要计算总数组的中间两位数
}
function getMidNum(nums1, start1, end1, nums2, start2, end2, key) {
const len1 = end1 - start1 + 1 //先获取传入的两个数组的长度，就如前边一样，我们始终要保持nums2长度大于nums1。
const len2 = end2 - start2 + 1
if(len1 > len2) {
return getMidNum(nums2, start2, end2, nums1, start1, end1, key) //递归终止，互换传入的数组
}
if(len1 === 0) { //len1已经不够了，直接计算剩下的key，返回nums2里的数据即可
return nums2[start2 + key - 1]
}
if(key === 1) { //已经逼近了最后的一位数，此时直接比较数组的start位即可。因为len2 > len1，且len1 !== 0，此时两个数组都必是有值的。
return Math.min(nums1[start1], nums2[start2])
}
//此时开始计算两个数组应该逼近的位数，
let i = start1 + Math.min(len1, parseInt(key / 2)) - 1
let j = start2 + Math.min(len2, parseInt(key / 2)) - 1
//比较数组，小的数组的start去掉（实际是更新start位置
if(nums1[i] > nums2[j]) {
return getMidNum(nums1, start1, end1, nums2, j + 1, end2, key - (j - start2 + 1))
}else {
return getMidNum(nums1, i + 1, end1, nums2, start2, end2, key - (i - start1 + 1))
}
}
};
代码设计的得很精妙。
用到了递归，因为是一次递归，所以空间复杂度实际上是O（1），且时间复杂度是log(m+n)。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
网友评论