首页 > 代码库 > 第1章第1节练习题10 查找中位数
第1章第1节练习题10 查找中位数
问题描写叙述
一个长度为L(L ≥1) 的升序序列S。处在第 ? L/2 ? 个位置的数称为S的中位数。比如,若序列
S1=(11,13,15,17,19) <script id="MathJax-Element-1" type="math/tex">S1=(11,13,15,17,19)</script>。则S1的中位数是15。
两个序列的中位数是含它们全部元素所组成的升序序列的中位数。比如,若
S2=(2,4,6,8,20) <script id="MathJax-Element-2" type="math/tex">S2=(2,4,6,8,20)</script>。则S1和S2的中位数是11。
如今有两个等长升序序列A和B,试设计一个在时间和空间都尽可能高效的算法。找出两个序列A和B的中位数。
算法思想
分别求两个升序序列A。B中位数,设为a和b
1). 若a=b,则a或b即为所求中位数,算法结束;
2). 若a<b。则舍弃序列A中较小的一半,同一时候舍弃序列B中较大的一半,要求两次舍弃的长度相等。
3). 若a>b,则设计序列A中较大的一半。同一时候设计序列B中较小的一半。要求两次舍弃的长度相等;
算法描写叙述
int FindMid(int A[], int B[])
{
int s1=0,d1=MaxSize-1,m1;
int s2=0,d2=MaxSize-1,m2;
while(s1!=d1||s2!=d2){
m1=(s1+d1)/2;
m2=(s2+d2)/2;
if(A[m1]<B[m2]){
if((s1+d1)%2==0){
s1=m1;
d2=m2;
}else{
s1=m1+1;
d2=m2;
}
}else if(A[m1]>B[2]){
if((s2+d2)%2==0){
d1=m1;
s2=m2;
}else{
d1=m1;
s2=m2+1;
}
}else{
return A[m1];
}
}
return A[s1]<B[s2]?A[s1]:B[s2];
}
详细代码见附件
附件
#include<stdio.h>
#define MaxSize 5
int FindMid(int*, int*);
int main(int argc,char* argv[])
{
int A[MaxSize]={11,13,15,17,19};
int B[MaxSize]={2,4,6,8,20};
int Num;
Num=FindMid(A,B);
printf("The mid Num is %d\n",Num);
return 0;
}
int FindMid(int A[], int B[])
{
int s1=0,d1=MaxSize-1,m1;
int s2=0,d2=MaxSize-1,m2;
while(s1!=d1||s2!=d2){
m1=(s1+d1)/2;
m2=(s2+d2)/2;
if(A[m1]<B[m2]){
if((s1+d1)%2==0){
s1=m1;
d2=m2;
}else{
s1=m1+1;
d2=m2;
}
}else if(A[m1]>B[2]){
if((s2+d2)%2==0){
d1=m1;
s2=m2;
}else{
d1=m1;
s2=m2+1;
}
}else{
return A[m1];
}
}
return A[s1]<B[s2]?A[s1]:B[s2];
}
第1章第1节练习题10 查找中位数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。