给定两个大小为 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
分析:
常规做法,是 O(m+n)
两个有序数组,合并成一个有序数组,取中位数,
思路很清晰
这里只要取中位数,只要保证,这个数字左边的元素个数(数组一左边 i 个 + 数组二左边 j 个)与右边的元素个数相等,这个数字左边的元素都小于右边的元素,
就可以认为,这个数字是我们想要的
先分片, 保证找到的中位数,这个数字左边的元素个数(数组一左边 i 个 + 数组二左边 j 个)与右边的元素个数相等
因为是中间位置的数字,
如果第一个数组 nums1 取 i 个,(0 <= i <= m),
那么第二个数组 nums2 里面取 j 个,(0 <= j <= n),
i 与 j 满足一定的关系 i + j = (m + n)/2
, 或者 i + j = (m + n + 1)/2
, 因为 m + n 可能是奇数,也可能是偶数。
那么 j = (m + n + 1) / 2 – i
再取值,这个数字左边的元素都小于右边的元素
i 和 j 把两个数组,各分成两片,出现了四个关键的数字,
数组一左边最大,num1LeftMax
数组一右边最小,num1RightMin
数组二左边最大,num2LeftMax
数组二右边最小,num2RightMin
如果 num1LeftMax <= num2RightMin, num2LeftMax <= num1RightMin, 就找到我们想要的中位数了,因为 num1 是有序数组,num1LeftMax 当然小于 num1RightMin,同样的 num2LeftMax < num2RightMin
O(m), 因为这就是二分搜索,搜索条件不是很直接
为什么是 O(m), 因为这就是二分搜索。
一般我们的二分搜索是一个有序数组,查找元素,每一次查找,把搜索范围缩减一半。通过移动上边界和下边界
就是比较条件相对简单,直接比元素大小
这道题其他与基础的二分查找一致,比较条件有些变化
如果 num1LeftMax > num2RightMin, 数字一左边的大了,就是 i 大了,就要移动右边界,就是右边界变小
(左边界只能右移,只能变大。右边界只能左移,只能变小)
其他情况,类似处理
拿起算法的钢笔,跑一遍
示例 3:
nums1 = [1, 3,8,9,15]
nums2 = [7,11,18,19,21,25]
中位数是 11
左边有 5 个元素,m = 5,
右边有 6 个,n = 6
数组一右边最小,num1RightMin < 数组二左边最大,num2LeftMax
就是 i 小了,左边界右移,low = 3
现在满足要求了,m + n 是奇数,左边多一个,选数组一左边最大和数组二左边最大中较大的,就是 11
拿起算法的钢笔,再跑一遍,为了印象深刻
示例 4:
nums1 = [23, 26,31,35]
nums2 = [3,5,7,9,11,16]
中位数是 13.5,11 和 16 的平均值
左边有 4 个元素,m = 4,
右边有 6 个,n = 6
数组一左边最大,num1LeftMax > 数组二右边最小,num2RightMin
就是 i 大了,右边界左移, high = 1
左边一个元素都不要,默认数组一左边最大为负无穷,num1LeftMax = Number.MIN_SAFE_INTEGER
,
现在满足要求了,m + n 是偶数,找出中间两个 11 与 16,求平均值为 13.5
PS: 个人看,看书和看算法动画,不错,就是少了一点参与感。
拿起钢笔,写写画画,需要保证结果一致嘛,我感觉,理解的好一些
代码如下:
选短的数组处理,处理快,还保证了 j 一定大于 0(因为 n > m),避免了一些逻辑处理。
里面处理了一些边界条件,i = 0, 第一个数组左边一个元素都不要,i = m, 第一个数组右边一个元素都不要
m + n 的值是奇数,这个好处理一点,只需要找出一个元素
m + n 的值是偶数,需要找出两个元素
var findMedianSortedArrays = function (nums1, nums2) {if (nums1.length > nums2.length) {[nums1, nums2] = [nums2, nums1]
}
const arr1Length = nums1.length, arr2Length = nums2.length;
let low = 0, high = arr1Length;
const halfLen = Math.floor((arr1Length + arr2Length + 1) / 2);
while (low <= high) {let i = Math.floor((low + high) / 2);
let j = halfLen - i;
let num1LeftMax = i == 0 ? Number.MIN_SAFE_INTEGER : nums1[i - 1]
let num1RightMin = i == arr1Length ? Number.MAX_SAFE_INTEGER : nums1[i]
let num2LeftMax = j == 0 ? Number.MIN_SAFE_INTEGER : nums2[j - 1]
let num2RightMin = j == arr2Length ? Number.MAX_SAFE_INTEGER : nums2[j]
if (num1LeftMax <= num2RightMin && num2LeftMax <= num1RightMin) {
var answer = 0
if (Math.round((arr1Length + arr2Length) % 2) == 1) {answer = Math.max(num1LeftMax, num2LeftMax)
}
else {// Math.round((arr1Length + arr2Length) % 2) == 0
let leftMax = Math.max(num1LeftMax, num2LeftMax)
let rightMin = Math.min(num1RightMin, num2RightMin)
answer = (leftMax + rightMin) / 2
}
return answer
}
else if (num1LeftMax > num2RightMin) {high = i - 1}
else { // num2LeftMax > num1RightMin
low = i + 1
}
}
return 0;
};
我还喜欢看视频,有一个 youtube , 链接是 https://www.youtube.com/watch… .
本文可以作为该视频和 Leatcode 官方题解的补充,官方题解: https://leetcode.com/problems…