两个序列的中位数(超详细的讲解)

问题描述:在两个等长的升序序列中找到两个序列的中位数,设s序列的长度为n(n>=1),称n/2个位置的数为s的中位数

  • 我在这里简单分享下自己对这道题的看法。暴力法这里不谈了,仅仅谈谈教材上的减治法思路,并且是如何实现出bug free的代码,而不会类似于二分查找那样陷入死循环!(下面的=究竟是赋值还是判定相等关系自行判断)

  • 教材上的算法思路
    分别求出两个序列的中位数,记为a和b;比较a和b,有下列三种情况:

① a = b:则a即为两个序列的中位数;

② a < b:则中位数只能出现在a和b之间,在序列A中舍弃a之前的元素得到序列A1,在序列B中舍弃b之后的元素得到序列B1;

③ a > b:则中位数只能出现在b和a之间,在序列A中舍弃a之后的元素得到序列A1,在序列B中舍弃b之前的元素得到序列B1;

在A1和B1中分别求出中位数,重复上述过程,直到两个序列中只有一个元素,则较小者即为所求。

  • 教材上的伪代码如下
    算法5.1:两个序列中位数SearchMid
    输入:两个长度为n的有序序列A和B
    输出:序列A和B的中位数

  • 循环直到序列A和序列B均只有一个元素
    1.1 a = 序列A的中位数;
    1.2 b = 序列B的中位数;
    1.3 比较a和b,执行下面三种情况之一:
    1.3.1 若a=b,则返回a,算法结束;
    1.3.2 若a<b,则在序列A中舍弃a之前的元素,在序列B中舍弃b之后的元素,转步骤1;
    1.3.3 若a>b,则在序列A中舍弃a之后的元素,在序列B中舍弃b之前的元素,转步骤1;

  • 序列A和序列B均只有一个元素,返回较小者;

    上述的算法的循环每次使A,B序列长度不断减少,直到满足while循环中的A,B序列各只剩一个元素,最后选择小者为正确答案。但是这个循环真的能做到每次使A,B序列长度减小吗?也就是说假如循环后A,B长度不变的话A,B不可能变成各只剩一个元素,最后永远也不会跳出而陷入死循环!那到底问题出在了哪里呢?
    A: [1,2]
    B: [-1,3]
    假如有这样一个样例,按照上面的算法,取A的中位数下标首尾下标相加除2得下标0,得到A的中位数1,同理取得B的中位数-1,即:
    a=1
    b=-1
    现在a<b,序列A中舍弃a之前的元素,序列B中舍弃B之后的元素,
    现在新的情况为
    A:[1,2]
    B:[-1]
    再求一次a,b
    a=1
    b=-1
    现在a<b,跟上次循环一样序列A中舍弃a之前的元素,序列B中舍弃B之后的元素,boom!这次不管是A还是B一个元素也没扔掉!下次循环仍将是这样的情况,这意味着A,B永远也不会像伪代码描述的那样能够满足退出循环的条件,A,B中都各只剩一个元素,永远循环,根本不能返回我们想要的答案。你也许会说我一眼就看出A,B两个序列的中位数明显就是1嘛!但是计算机不是人,必须按照你写的代码运算从而得到答案。你也许会想到我直接写个if判断从而退出循环嘛!但是如果如果输入这个样例时A,B输入对调呢?你的if还能应付新的样例吗?而且万一有其它样例能使你的样例陷入死循环呢?if也许能解决问题,但这样会使我们的代码臃肿且不够优雅,关键是容易错,所以我们需要从理论上详细推导我们的循环到底在哪里出错了,从而写出真正可用的code

  • 我现在详细的推导一下这个循环问题到底出现在哪里
    初始化:
    设序列A: leftA=0,rightA=n-1,midA为A中间元素下标
    设序列B: leftB=0,rightB=n-1,midB为B中间元素下标

    注:n为两个等长序列长度,left,right,mid均为下标
    循环开始 A,B序列初始区间[0,n-1]
    循环:
    while(leftA<=righA&&leftB<=rightB)
    { //这里的循环条件先假定是这样,后面仔细探讨循环条件该填什么
    midA=(leftA+rightA)/2
    a=A[midA]
    midB=(leftB+rightB)/2
    b=B[midB]

    如果 a==b
    return a //两个中位数相等,直接返回

    如果 a<b
    ① 中位数大小范围应为为[a,b],说明中位数应该位于A中的[midA,rightA]中或者位于B中的[midB,rightB]

    ② 对于A序列,舍弃[leftA,midA-1],序列减小长度为(midA-1)-leftA+1=midA-leftA>=0,当midA-leftA=0时,A的减小长度为0,此时如果不干预将陷入死循环
    当midA-leftA=0时,根据midA的定义,此时midA=(leftA+rightA)/2=leftA
    解得leftA=rightA
    此时使leftA=midA,得到新的A序列[leftA,rightA]

    ③ 对于B序列,舍弃[midB+1,rightB],序列减小长度为rightB-(midB+1)+1
    =rightB-midB>=0,当等式为0时有midB=rightB,根据midB的定义,有
    (leftB+rightB)=rightB,跟② 类似,使这个等式成立的一个解为leftB=rightB
    其实还有一个解是,rightB=leftB+1,为什么呢?其实是这样:
    (rightB+leftB)/2=(leftB+1+leftB)/2=(leftB+leftB)/2+1/2=leftB
    原来是我们没意识到计算机在整数运算中对结果向下取整了,其实也就是直接丢掉了小数
    上面的推导告诉了我们对于B序列,一旦
    (1)rightB=leftB或者 (2)rightB=leftB+1
    B的长度永远也不会减小,对于(2)情况,可以看出此时的B长度为2,里面就两个元素,意味着B在长度为2死就陷入了死循环,这似乎就解释了
    A: [1,2]
    B: [-1,3]
    这个样例为什么会陷入死循环,此时必须干预死循环,(2)出现的比(1)早,只需考虑(2),我们可以在while循环了写leftB+1<right从而避免出现(2)的情况从而跳出循环
    现在使rightB=midB,得到新的B序列 [leftB,rightB]

    如果 a>b
    ① 中位数大小范围应为为[b,a],说明中位数应该位于A中的[leftA,midA]中或者位于B中的[midB,rightB]
    ② 对于A序列,舍弃区间[midA+1,rightA],减小长度rightA-(midA+1)-1=
    rightA-midA>=0,当leftA==rightA时等式为0
    使rightA=midA,获得新的A序列[leftA,rightA]
    ③ 对于B序列,舍弃区间[leftB,midB-1],减小长度midB-1-leftB+1=
    midB-leftB>=0,当rightB==leftBrightB==leftB+1时等式为0
    使leftB=midB,获得新的B序列[leftB,rightB]
    }
    终止:
    本来按照教材中的算法伪代码,while循环的条件时直到A,B都仅剩一个元素时跳出,此时while应写成
    while(leftA<rightA || leftB<rightB)即可
    跳出循环后,leftA=rightA&&leftB=rightB
    但是根据上面的分析rightA=leftA+1和rightB=leftA+1时,A,B的长度永远卡死在了2,根本不可能满足跳出循环要求(rightA=leftA和rightB=leftB已经不用管了)因此为了能正确的跳出循环,while应改成
    while(leftA+1<rightA || leftB+1<rightB)
    跳出循环后,leftA+1=rightA&&leftB+1=rightB

  • 现在我们讨论一下跳出循环后的答案怎么求
    显然如果初始输入的A,B的长度要么都大于等于2,要么都为1
    当n>=2时,退出循环后A,B两个序列都各只剩2各元素,中位数都在4个候选元素中
    当n==1时,根据上文写的while,不会进入循环,中位数位于2个候选元素中
    对于上面两种情况,一种简单的求中位数的办法是直接合并两个有序序列,由于合并后的序列要么长度为4要么为2,合并是常数级操作,因此时间可以忽略,实际上我也是这样做的

  • java示例代码:

class Solution { 
    public static void main(String[] args) { 
        int[] A = new int[]{ 1,2};
        int[] B = new int[]{ -1,3};
        int temp = searchMid(A, B);
    }

    private static int searchMid(int[] A, int[] B) { 
        int leftA = 0, rightA = A.length - 1;//定义leftA,rightA指明序列A的范围
        int leftB = 0, rightB = B.length - 1;//定义leftB,rightB指明序列B的范围
        while (leftA + 1 < rightA || leftB + 1 < rightB) { //跳出循环后leftA+1==rightA&&leftB+1==rightB
            int midA = (leftA + rightA) / 2;
            int a = A[midA];
            int midB = (leftB + rightB) / 2;
            int b = B[midB];
            if (a < b) { 
                leftA = midA;//rightA==leftA || rightA=leftA+1时缩减长度为0
                rightB = midB;//rightB==leftB时缩减长度为0
            } else if (a > b) { 
                rightA = midA;//rightA==leftA时缩减长度为0
                leftB = midB;//rightB==leftB || rightB==leftB+1时缩减长度为0
            } else { 
                return a;
            }
        }
        int[] temp = new int[4];//定义最大长度为4的零时数组,存储2个或4个元素的合并序列
        int index = 0;
        while (leftA <= rightA && leftB <= rightB) { //两个升序序列的合并操作
            if (A[leftA] < B[leftB]) { 
                temp[index++] = A[leftA++];
            } else { 
                temp[index++] = B[leftB++];
            }
        }
        while (leftA <= rightA) { 
            temp[index++] = A[leftA++];
        }
        while (leftB <= rightB) { 
            temp[index++] = B[leftB++];
        }
        index--;//index自检后指向合并序列的最后一个元素,方便下标运算求出中位数
        return temp[index / 2];//返回中位数
    }
}
  • 时间复杂度,每次循环A,B个减少一半长度,总共循环logn次,最后在2个或4个候选元素得出中位数,常数级操作,故时间复杂度为O(logn)
  • 总结:该算法的思路很简单,就是根据两个序列的中位数对比结果,对应抛弃A和B的左或右边序列,在剩下的序列里继续寻找目标,跟二分法类似,思想很简单,但是真正写出bug free的code却不简单,需要仔细地推导才能保证我们的循环是正确的,不会死循环。正巧我的教材上只给出了这个问题的伪代码,并没有给出具体的实现,或许作者自己也只是纸上谈兵并没有去实践过呢?
  • 建议:为什么我会想到这个算法会陷入死循环却又能正确的找到解决办法的呢?我为什么会想到这样分析呢?其实是源于我当初写二分查找,始终写不出正确的代码,就是因为循环条件不清晰,像上面一样很容易陷入死循环,没有正确的分析,大学老师当时讲课也只是像教材一样介绍了思想却并没有讲解细节,我很怀疑他自己写不看书能不能正确的写出二分查找算法来。二分查找有很多变种,比如给定一个非降序序列,找出第一个大于或者最后一个大于目标值target的数的下标,看大家能不能写出正确的程序来。这里给大家介绍一个概念:循环不变式,能帮助我们分析自己的程序
    这里贴两个链接,跟上文的中位数问题和二分查找有关,使用了循环不变式这个概念,我觉得很有用,强烈建议大家看看
    利用循环不变式写出正确的二分查找及其衍生算法
    如何写出正确的二分查找?——利用循环不变式理解二分查找及其变体的正确性以及构造方式
    如有错误希望大家指出谢谢!可能有些细节写的不对,但是大家看完我的分析了解了我的思路是应该能分析出我哪里细节写错了。
    原文作者:weixin_40564024
    原文地址: https://blog.csdn.net/weixin_40564024/article/details/106910305
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞