引言：用Js攻略leetcode中的算法，將會介紹自己的思路和注意點，一邊學(xué)習(xí)一邊愉快刷題呀。
問題：
給定兩個大小為 m 和 n 的有序數(shù)組 nums1 和 nums2 。
請找出這兩個有序數(shù)組的中位數(shù)。要求算法的時間復(fù)雜度為 O(log (m+n)) 。
你可以假設(shè) nums1 和 nums2 不同時為空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
中位數(shù)是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
中位數(shù)是 (2 + 3)/2 = 2.5
思考:
總體思考：
最主要的難點是算法復(fù)雜度的限制， log級別的時間復(fù)雜度我們自然想到二分法，每次取中間值，自然得出的是log2(n)級別的。
因為nums1和nums2是有序數(shù)組，我們對這兩個數(shù)組分別在某一位置進行劃分。
比如nums1數(shù)組設(shè)為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數(shù)組設(shè)為B，劃分位置為 j :
left_B | right_B
B [0]，B [1]，...，B [j-1] | B [j]，B [j + 1]，...，B [n-1]
這樣左邊有 j 個元素，右邊有（ n - j ）個元素。
把兩個數(shù)組的左右兩邊分別混合，也就是left_A和left_B放一起，right_A和right_B放一起，得到中位數(shù)需要滿足下面兩個條件：
- 左右數(shù)量相等（偶數(shù)：i + j = m - i + n -j ）或者左邊比右邊大一個（奇數(shù)：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
那么對于總長度為奇數(shù)，中位數(shù) = max(left_A, left_B)；對于總長度為偶數(shù)，中位數(shù) = ( max(left_A, left_B) ，min(right_A，right_B) ) / 2
把上面兩個條件進行整理：
-
i = 0?m，j = parseInt( (m + n + 1) / 2) - i (奇偶通用，陰影劃分的為左邊，其他為右邊)
總長度為奇數(shù)
總長度為偶數(shù)
所以n要大于等于m（n>=m），這樣確保 j 是合法索引。
- shortArray[ i -1] <= longArray[ j ]，longArray[ j - 1 ] <= shortArray [ i ]
實現(xiàn)細(xì)節(jié)：
- 先對nums1和nums2的長度進行判斷，選擇長的作為longArray， 短的作為shortArray
- i 在 [ 0, m ]中進行取值，并根據(jù)二分法取中值，j = parseInt( (m + n + 1) / 2) - i
- 如果（ j > 0 && i < m && longArray[j-1] > shortArray[i] ），說明shortArray [i]太小，i 應(yīng)該繼續(xù)增大，取值范圍變?yōu)?[ i + 1, m ]
- 如果（ i > 0 && j < n && shortArray[i-1] > longArray[j] ），說明shortArray [i]太大， i 應(yīng)該減小，取值范圍變?yōu)閇0, i - 1]
- 以此循環(huán)，直到上面條件都不滿足，說明要么取到邊界了（i =0 , j=0 等情況），要么shortArray和longArray左邊都取了值，要選出shortArray和longArray左邊最大的值。
-
(i =0 情況下，左側(cè)確定，左邊最大值為longArray[j - 1] )
image.png -
(j = 0情況下，左側(cè)確定，左側(cè)最大值為shortArray[i - 1])
image.png -
(其他情況，shortArray和longArray左邊都取了值)
image.png
- 對于總長度為奇數(shù)， 中位數(shù) = max(left_A, left_B)， 也就是第5步得到的值。如果是奇數(shù)，要再得到 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;
}
//假設(shè)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);
//兩數(shù)組相加個數(shù)是奇數(shù)，只要取中間值
if( (m + n)%2 == 1 ) return maxLeft;
//個數(shù)是偶數(shù)，必須左右兩邊中位數(shù)相加除以二
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;
}
