javascript初探LeetCodeの4.Median of Two Sorted Arays

テーマ
The e e re re two sorted arrays nums 1 and nums 2 of size m and n respively.Find the median of the two sorted arrays.The overall run time complexity shound be O(log(m+n).
example

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

分析
これはleetcodeの4番の問題です.難易度はhardです.つまり、2つの配列の中間値です.暴力的アプローチは、2つのグループを秩序化配列にまとめて並べ替えることであり、次いで中央値を見つけることができるが、時間複雑度O(m*n)、空間複雑度O(m+n).問題が要求される時間複雑度O(log (m+n))は、アルゴリズムの時間複雑さの中にlogがあり、分治法を使用した思想が多い.
AとBの二つの秩序配列を考慮する:

1、Aの中央値がBの中央値より小さい場合、AとBが合わせた後の中央値はAの後半とBの前半に必ず存在します.

、Aの中央値がBの中央値より大きい場合、AとBの中間値はAの前半とBの後半に必ず存在します.

3、Aの中央値がBの中央値に等しい場合、AとBの中央値はAの中央値に等しく、Bの中央値にも等しい.このようにして、AとBの間の中央値を縮小し続けることができます.これも二分再帰の主要な思想であり、より細いのはコードに注釈があります.

js実現
コメントなし:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var getMedian = function(arr1,start1,len1,arr2,start2,len2,k){
    if(len1 - start1 > len2 -start2)
        return getMedian(arr2, start2, len2, arr1, start1, len1, k);
    if(len1 - start1 == 0)
        return arr2[k - 1];
    if(k == 1)
        return arr1[start1] > arr2[start2] ? arr2[start2] : arr1[start1]; 
    var p1 = start1 + (len1 - start1 < parseInt(k / 2) ? len1 - start1 : parseInt(k / 2)); 
    var p2 = start2 + k - p1 + start1;
    if(arr1[p1 - 1] < arr2[p2 - 1])
        return getMedian(arr1,  p1, len1, arr2, start2, len2, k - p1 + start1);
        else if(arr1[p1 - 1] > arr2[p2 -1])
            return getMedian(arr1, start1, len1, arr2, p2, len2, k - p2 + start2);
        else
            return arr1[p1 - 1];
}
var findMedianSortedArrays = function(nums1, nums2) {
    var len1 = nums1.length;
    var len2 = nums2.length;
    var size = len1 + len2;
    if(size % 2 == 1)
        return getMedian(nums1, 0, len1, nums2, 0, len2, parseInt(size / 2 + 1));
    else
        return (getMedian(nums1, 0, len1, nums2, 0, len2, parseInt(size / 2)) + getMedian(nums1, 0, len1, nums2, 0, len2, parseInt(size / 2 + 1))) /2;
};

コメント付き:

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var getMedian = function(arr1,start1,len1,arr2,start2,len2,k){
/*
   k              k  ，       ，        parseInt(size / 2 + 1)     parseInt(size / 2)  。
                arr1 arr2    k  。start1 start2         
  k = k -                           
*/
    if(len1 - start1 > len2 -start2)
        //           arr1      ，             
        return getMedian(arr2, start2, len2, arr1, start1, len1, k);
    if(len1 - start1 == 0)
        //  arr1              0，        k       arr2 ，arr2  ，    arr2[k - 1]
        return arr2[k - 1];
    if(k == 1)
        //     if  ，         A B ，    k     。
        //       1  ，     arr1 arr2          ，       。
        return arr1[start1] > arr2[start2] ? arr2[start2] : arr1[start1]; 
    var p1 = start1 + (len1 - start1 < parseInt(k / 2) ? len1 - start1 : parseInt(k / 2)); //arr1      ，  arr1        ，        
    var p2 = start2 + k - p1 + start1;//arr2      
    if(arr1[p1 - 1] < arr2[p2 - 1])//      index 0  ，    ，  if、if else else                 
        return getMedian(arr1,  p1, len1, arr2, start2, len2, k - p1 + start1);
        else if(arr1[p1 - 1] > arr2[p2 -1])
            return getMedian(arr1, start1, len1, arr2, p2, len2, k - p2 + start2);
        else
            return arr1[p1 - 1];
}
var findMedianSortedArrays = function(nums1, nums2) {
    var len1 = nums1.length;
    var len2 = nums2.length;
    var size = len1 + len2;
    if(size % 2 == 1)
        //  A B       ，        
        return getMedian(nums1, 0, len1, nums2, 0, len2, parseInt(size / 2 + 1));
    else
        //  A B       ，              
        return (getMedian(nums1, 0, len1, nums2, 0, len2, parseInt(size / 2)) + getMedian(nums1, 0, len1, nums2, 0, len2, parseInt(size / 2 + 1))) /2;
};

締め括りをつける
再帰的に問題の規模を縮小することによって、効率は暴力的な帰順よりも高くなりますが、配列長のパリティと境界にも注意が必要です.また、jsのk/2は自動的に整理されないので、parseIntで処理してください.