【JS攻略Leetcode】No.4. median-of-tw
引言:用Js攻略leetcode中的算法,将会介绍自己的思路和注意点,一边学习一边愉快刷题呀。
问题:
给定两个大小为 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
思考:
总体思考:
最主要的难点是算法复杂度的限制, log级别的时间复杂度我们自然想到二分法,每次取中间值,自然得出的是log2(n)级别的。
因为nums1和nums2是有序数组,我们对这两个数组分别在某一位置进行划分。
比如nums1数组设为A, 划分位置为 i :
left_A | right_A
A [0],A [1],...,A [i-1] | A [i],A [i + 1],...,A [m-1]
这样左边有 i 个元素,右边有( m - i )个元素。
nums2数组设为B,划分位置为 j :
left_B | right_B
B [0],B [1],...,B [j-1] | B [j],B [j + 1],...,B [n-1]
这样左边有 j 个元素,右边有( n - j )个元素。
把两个数组的左右两边分别混合,也就是left_A和left_B放一起,right_A和right_B放一起,得到中位数需要满足下面两个条件:
- 左右数量相等(偶数:i + j = m - i + n -j )或者左边比右边大一个(奇数:i + j = m - i + n -j + 1)
- max(left_A) 小于 min(right_B),而且max(left_B) 小于 min(right_A),因为left_A肯定小于right_A, left_B肯定小于right_B
那么对于总长度为奇数,中位数 = max(left_A, left_B);对于总长度为偶数,中位数 = ( max(left_A, left_B) ,min(right_A,right_B) ) / 2
把上面两个条件进行整理:
-
i = 0〜m,j = parseInt( (m + n + 1) / 2) - i (奇偶通用,阴影划分的为左边,其他为右边)
总长度为奇数
总长度为偶数
所以n要大于等于m(n>=m),这样确保 j 是合法索引。
- shortArray[ i -1] <= longArray[ j ],longArray[ j - 1 ] <= shortArray [ i ]
实现细节:
- 先对nums1和nums2的长度进行判断,选择长的作为longArray, 短的作为shortArray
- i 在 [ 0, m ]中进行取值,并根据二分法取中值,j = parseInt( (m + n + 1) / 2) - i
- 如果( j > 0 && i < m && longArray[j-1] > shortArray[i] ),说明shortArray [i]太小,i 应该继续增大,取值范围变为 [ i + 1, m ]
- 如果( i > 0 && j < n && shortArray[i-1] > longArray[j] ),说明shortArray [i]太大, i 应该减小,取值范围变为[0, i - 1]
- 以此循环,直到上面条件都不满足,说明要么取到边界了(i =0 , j=0 等情况),要么shortArray和longArray左边都取了值,要选出shortArray和longArray左边最大的值。
-
(i =0 情况下,左侧确定,左边最大值为longArray[j - 1] )
image.png -
(j = 0情况下,左侧确定,左侧最大值为shortArray[i - 1])
image.png -
(其他情况,shortArray和longArray左边都取了值)
image.png
- 对于总长度为奇数, 中位数 = max(left_A, left_B), 也就是第5步得到的值。如果是奇数,要再得到 minRight.
代码:
var findMedianSortedArrays = function(nums1, nums2) {
var shortArray = [],longArray = [], m = nums1.length, n = nums2.length,
temp = 0, maxLeft = 0, minRight = 0;
//保证 n >= m
if(m > n) {
shortArray = nums2;
longArray = nums1;
temp = m;
m = n;
n = temp;
} else {
shortArray = nums1;
longArray = nums2;
}
//假设shortArray取i个,longArray取parseInt((m+n+1)/2)-i个
var imin = 0, imax = m, i, j;
do {
i = parseInt((imin + imax)/2);
j = parseInt((m + n + 1)/2 - i);
if(j > 0 && i < m && longArray[j-1] > shortArray[i]) {
// shortArray和longArray左右都取了值,且i值取小了
imin = i + 1;
} else if( i > 0 && j < n && shortArray[i-1] > longArray[j]) {
// shortArray和longArray左右都取了值,且i值取大了
imax = i - 1;
} else {
// 考虑边界情况
if(i == 0) {
maxLeft = longArray[j - 1];
} else if (j == 0 ) {
maxLeft = shortArray[i - 1];
} else {
// i值不小不大, 也就是(shortArray[i-1] <= longArray[j] && longArray[j-1] <= shortArray[i])
maxLeft = Math.max(shortArray[i - 1], longArray[j -1]);
}
break;
}
} while (imin <= imax);
//两数组相加个数是奇数,只要取中间值
if( (m + n)%2 == 1 ) return maxLeft;
//个数是偶数,必须左右两边中位数相加除以二
if(i == m) {
minRight = longArray[j];
} else if(j == n){
minRight = shortArray[i];
} else {
minRight = Math.min(shortArray[i], longArray[j]);
};
return (maxLeft + minRight)/2;
}