Leetcode 编程训练[4]:Median of Two Sorted Arrays

#4:这次的题目比较难:找到两个有序数组A(大小为m)、B(大小为n)的中位数,并且整体时间复杂度为O(log(m+n))。查看提示,这道题与分治法、二分查找有关。

  1. 二分查找
    在计算机科学中,二分查找是在一个有序的数组中寻找目标元素。在每一次查找中,它都会将目标元素与数组中的中间元素进行比较;如果不相等,则取数组的一半再与目标元素进行下一轮查找。这个过程就有分治法的思想:每一次查找步骤就将大问题(一个数组内查找)分解为小问题(这个数组的一半查找)。

  2. 别人的分享
    MissMary女士提供了一种解法。将数组A、B分割成两部分。将比较小的那一组作为leftPart,比较大的那一组作为rightPart。如果我们能保证leftPart与rightPart的大小相等或相差一相等,并且leftPart所有元素比rightPart的所有元素小,就能很容易找到中位数了。

    转换成代码就是:

    • 条件一:(i + j == m - i + n - j) || (i + j == m - i + n - j + 1)
    • 条件二:A[i] >= B[j - 1] && A[i - 1] <= B[j]

    我们在满足条件一的情况下去寻找能满足条件二的结果,通过移动i的位置来寻找结果。如果当前情况下,不满足条件二,就通过二分查找地方式缩小一半的范围。这就需要创建一个标志位,我们将i的范围限定到[iMin, iMax]。当不满足A[i] >= B[j - 1]时,将继续搜索position i的右边(将iMin更新为i+1);同理,当不满足A[i - 1] <= B[j]时,将继续搜索position i的左边(将iMax更新为i-1)。

    整个循环体大概就是这样

    while(iMin <= iMax){
        //确定本次循环i,j值,满足第一条件
        i = parseInt((iMin + iMax) / 2);
        //m + n + 1保证取余后j不会小于0
        j = parseInt((m + n + 1) / 2) - i;
        //当A[i] < B[j - 1]时,搜索A[]右半边
        if(A[i] < B[j - 1]){
            iMin = i + 1;
        }else if(A[i - 1] > B[j]){
            iMax = i - 1;
        }else{
            //当满足第二条件:,即A[i] >= B[j - 1]、A[i - 1] <= B[j]
            //作下一步处理
        }
    

    我们添加一下边界值的情况,不让错误的位置出现。

    //考虑边界值的情况,使i、j-1有效,A[i] < B[j - 1]时,搜索A[]右半边
    if(j > 0 && i < m && A[i] < B[j - 1]){
        iMin = i + 1;
    }else if(i > 0 && j < n && A[i - 1] > B[j]){
        iMax = i - 1;
    }else{  
    

    最后,还需要返回结果。当m+n=奇数时,leftPart比rightPart多一个数,leftPart的右边界就是中位数的位置。并且当i=0时,A[]全体大于B[],中位数就是B[j-1];同理当j=0时,中位数就是A[i-1]。在满足条件二的情况下,我们有4个不等式:A[i-1]<=A[i],B[j-1]<=B[j],A[i]>=B[j-1],A[i-1]<=B[j]。得出A[i-1]与B[j-1]中大的那个数就是中位数。我们取个最大值即可Math.max(A[i - 1], B[j - 1])。

    当m+n=偶数时,我们需要取中间两个数的平均值。并且当i=m时,A[]全体小于于B[],中位数就是B[j];同理当j=n时,中位数就是A[i]。否则为rightPart的左边界值中的最小值Math.min(A[i], B[j])。最后再取个平均就可以了。

    if(i === 0){
        candLeftPart = B[j - 1];
    }else if(j === 0){
        candLeftPart = A[i - 1];
    }else{ 
        candLeftPart = Math.max(A[i - 1], B[j - 1]);
    }
    //整体大小为奇数
    if((m + n) % 2 == 1){
        return candLeftPart;
    }  
    //整体大小为偶数
    if(i == m){
        candRightPart = B[j];
    }else if(j == n){
        candRightPart = A[i];
    }else{
        candRightPart = Math.min(A[i], B[j]);
    }
    return (candLeftPart + candRightPart) / 2;
    

    这种方案只用到了二分查找,对于分治还没有利用,不过时间复杂度O(log(min(m,n)))。有种使用O(log(m+n))的解法与合并排序的流程有点类似。每调用一次划分函数,查询规模都减少一半。就是本方法的迭代方法。


源码