005.md

两数组第K值

JS实现

版本一

function findKth(ary1,ary2,k) {
    // body...
    var high1 = ary1.length-1,
        high2 = ary2.length-1,
        mid1 = 0,
        mid2 = 0,
        low1=0,
        low2=0;
    if (k<1 || k>ary1.length+length) {return false;}
    while(true){        
        mid1 = low1+parseInt((high1-low1)/2);
        mid2 = low2+parseInt((high2-low2)/2);
        if (mid1+mid2+1 > k) {
            high1 = mid1-1;
            high2 = mid2-1;
        }else if (mid1+mid2+1 < k) {
            if (ary1[mid1] < ary2[mid2]) {
                low1 = mid1+1;
                low2 = mid2;
            }else{
                low1 = mid1;
                low2 = mid2+1;
            }
        }else{
            break;
        }
    }
    if (ary1[mid1] < ary2[mid2]) {
        return ary1[mid1];
    }else{
        return ary2[mid2];
    }
}

版本二

function findKth(ary1,ary2,k) {
    // body...
    var m = ary1.length,
        n = ary2.length;
    if (m>n) {findKth(ary2,ary1,k)}
    var low = 0,
        high = m-1,
        mid = 0,
        j = 0;
    while(low <= high){
        mid = low + parseInt((high-low)/2);
        j = k-1-mid;
        if (j > n-1 || ary2[j] > ary1[mid]) {
            low = mid + 1;
        }else{
            if(low == high){
                break;
            }else{
                high = mid;
            }
        }
    }
    var chech1 = low-1 >= 0?ary1[low-1]:Number.NEGATIVE_INFINITY;
    var check2 = k-1-low >=0?ary2[k-1-low]:Number.NEGATIVE_INFINITY;
    return Math.max(chech1,check2);
}

注：

1、版本二的效率更快，为log(min(m,n)).

测试用例

ary1 = [1,6,7,8,12,15];
ary2 = [3,4,9,10,16,20,25];

预期结果

console.log(findKth(ary1,ary2,10));//应该返回元素15