找出两个序列的中位数

一个长度为L（L>=1）的升序序列S，处在L/2(向上取整）个位置的数称为S的中位数。例如，若序列S1={11,13,15,17,19}，则S的中位数是15，两个序列的中位数是含他们所有元素的升序序列的中位数。例如，若S2={2,4,6,8,20}，则S1和S2的中位数是11。现在有两个等长升序序列A个B，试找出两个序列A和B的中位数。

方法一：

思想：先进行合并，然后找出合并后这个表的中位数。

代码：

bool merge(SqList &A，SqList &B,SqList &C) {if(A.length + B.length > MaxSize){return false;}int indexA=0,indexB=0;indexC=0;while(index < A.length && indexB < B.length){//归并两个表 if(A.data[indexA] <= B.data[indexB]){C.data[indexC++]=A.data[indexA++];}else{C.data[indexC++]=B.data[indexB++];}}while(index < A.length){//A表有剩余 C.data[indexC++]=A.data[indexA++];}while(indexB < B.length){//B表有剩余 C.data[indexC++]=B.data[indexB++];}//表C的长度 C.length=indexC;return true;
}bool getMid(SqList &A,SqList &B,ElemType &x){if(A.length != B.length || A.length <=0){//合法性判断 return false;}//进行归并排序 SqList C;merge(A,B,C);//返回中位数 x=C.data[C.length/2-1];return true;
}

时间复杂度O(n)；空间复杂度O（1）

方法二：

对于本题来说，合并后的序列一定是偶数个。中位数左边的数均比它小，右边的数均比它大，在中位数的左边和右边同时删除或增加等长的元素，中位数不会改变。

思想：求两个升序序列A和B的作为数，将A的中位数设为midA，B的中位数设为midB。

当midA=midB时，midA或midB为中位数，算法结束。

当midA<midB时，舍弃A中较小的一半，舍弃B中交大的一半，舍弃的元素个数相同。

当midA>midB时，舍弃B中较小的一半，舍弃A中交大的一半，舍弃的元素个数相同。

重复上述过程，知道两个序列中均只有一个元素时，较小的为两个序列的中位数。

代码：

bool getMid(SqList &A,SqList &B,ElemType &x){if(A.length != B.length || A.length <=0){//合法性判断 return false;}int i,di,midA,j,dj,midB;i=0;//表示表A开始时的下标 di=A.length-1;//表示表A最后一个元素的下标 j=0;//表示表B开始时的下标 dj=B.length-1;//表示表B最后一个元素的下标 while(i != di || j != dj){//两个表中的元素都超过一个元素时，大于等于2，均只有一个元素时，选择最小的即可 //中位数下标 midA=(i+di)/2;midB=(j+dj)/2;//表A和标B的中位数相等时，找到两个表的中位数 if(A.data[midA]==B.data[midB]){x=A.data[midA];return true;} else if(A.data[midA]<B.data[midB]){//表A的中位数小于表B的中位数时，舍弃表A较小的一半，舍弃表B较大的一半dj=midB;i=(di+midA)%2 ==0 ? midA:(midA+1);} else{//表A的中位数大于表B的中位数时，舍弃表A较大的一半，舍弃表B较小的一半di=midA;j=(di+midB)%2 == 0 ? midB:(midB+1); }} x=A.data[i] < B.data[j] ? A.data[i]:B.data[j];//两个表中只剩下一个元素时，中位数为最小的一个。 
}

时间复杂度O（logn）空间复杂度O(1)