【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放一起，得到中位数需要满足下面两个条件：

1. 左右数量相等（偶数：i + j = m - i + n -j ）或者左边比右边大一个（奇数：i + j = m - i + n -j + 1）
2. 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

把上面两个条件进行整理：

1. i = 0〜m，j = parseInt( (m + n + 1) / 2) - i (奇偶通用，阴影划分的为左边，其他为右边)

   
   总长度为奇数
   总长度为偶数
   

   所以n要大于等于m（n>=m），这样确保 j 是合法索引。

2. shortArray[ i -1] <= longArray[ j ]，longArray[ j - 1 ] <= shortArray [ i ]

实现细节：

1. 先对nums1和nums2的长度进行判断，选择长的作为longArray， 短的作为shortArray
2. i 在 [ 0, m ]中进行取值，并根据二分法取中值，j = parseInt( (m + n + 1) / 2) - i
3. 如果（ j > 0 && i < m && longArray[j-1] > shortArray[i] ），说明shortArray [i]太小，i 应该继续增大，取值范围变为 [ i + 1, m ]
4. 如果（ i > 0 && j < n && shortArray[i-1] > longArray[j] ），说明shortArray [i]太大， i 应该减小，取值范围变为[0, i - 1]
5. 以此循环，直到上面条件都不满足，说明要么取到边界了（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

6. 对于总长度为奇数， 中位数 = 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;
}