题目:设计一个高效算法,求两个等长为L的升序序列A和B
的中位数。
例如:S1=(11,13,15,17,19)
S2=(2,4,6,8,20)
则S1和S2的中位数是11。
1)问题分析1:
简单的算法是将两个升序序列归并排序,然后求其中位数
算法的时间复杂度和空间复杂度均为0(n)
2)问题分析2:
利用归并排序的思想对A和B的元素逐个访问,同时计数,当访问到第L个元素时即为所求。
算法时间、空间复杂度分别为O(n), O(1)
3)问题分析3:
分别求A和B的中位数a和b。
(1)若a=b,则a或b即为所求。
(2)若a<b,舍弃a所在序列A中的较小一半,同时舍弃b中所在序列B较大一半,两者舍弃的元素个数相等,在保留的两个升序序列中继续求中位数a和b。
(3)重复上述过程,直至两个序列中只含有一个元素为止,较小者即为所求。
算法时间、空间复杂度分别为O(log2`n), O(1)
综合算法
int search1(int a[],int b[],int n)
{
int c[2*n];
int i=0,j=0;
int count=0;
while(i<n&&j<n)
{
if(a[i]<b[j])
c[count++]=a[i++];
else if(a[i]>b[j])
c[count++]=b[j++];
else
{
c[count++]=a[i];
++i;
++j;
}
}
while(i<n)
{
c[count++]=a[i++];
}
while(j<n)
{
c[count++]=b[j++];
}
return c[n-1];
}
int search2(int a[],int b[],int n)
{
int i=0,j=0,count=1;
while(count!=n)
{
if(a[i]<b[j])
++i;
else
++j;
count++;
}
return a[i]<=b[j]?a[i]:b[j];
}
int search3(int a[],int b[],int n)
{
int s1,e1,mid1,s2,e2,mid2;
s1=0;//start
e1=n-1;//end
s2=0;
e2=n-1;
while(s1!=e1||s2!=e2)
{
mid1=(s1+e1)/2;
mid2=(s2+e2)/2;
if(a[mid1] == b[mid2])
return a[mid1];
if(a[mid1]<b[mid2])//分别考虑奇数和偶数,保持两数组个数相等
{
if((s1+e1)%2 == 0)
{
s1=mid1;//舍弃a中间节点以前部分
e2=mid2;//舍弃b中间节点以后部分
}
else //元素个数为偶数个
{
s1=mid1+1;
e2=mid2;
}
}
else
{
if((s1+e1)%2 == 0)
{
e1=mid1;//舍弃a中间节点以前部分
s2=mid2;//舍弃b中间节点以后部分
}
else //元素个数为偶数个
{
e1=mid1;
s2=mid2+1;
}
}
}
return (a[s1]<b[s2]?a[s1]:b[s2]);
}
int main()
{
int s1[5]={11,13,15,17,19};
int s2[5]={2,4,6,8,20};
cout<<"select which solution"<<endl;
cout<<"1,归并"<<endl;
cout<<"2,计数"<<endl;
cout<<"3,中位数比较"<<endl;
int n;
cin>>n;
switch(n)
{
case 1:cout<<search1(s1,s2,5)<<endl;break;
case 2:cout<<search2(s1,s2,5)<<endl;break;
case 3:cout<<search3(s1,s2,5)<<endl;break;
default :break;
}
return 0;
}