首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为L(L≥1)的升序序列S,处在第个位置的数称为s的中位数。例如,若序列S1=(11,13,15,17,19),则Sl的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2=(2,4,6,8,20),则Sl和S2的中位数是
一个长度为L(L≥1)的升序序列S,处在第个位置的数称为s的中位数。例如,若序列S1=(11,13,15,17,19),则Sl的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2=(2,4,6,8,20),则Sl和S2的中位数是
admin
2015-12-30
82
问题
一个长度为L(L≥1)的升序序列S,处在第
个位置的数称为s的中位数。例如,若序列S1=(11,13,15,17,19),则Sl的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若S2=(2,4,6,8,20),则Sl和S2的中位数是11。现有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。
要求:
根据设计思想,采用C或C++或Java语言描述算法,关键之处给出注释。
选项
答案
算法的实现如下: int M Search(int A[],intB[],int n){ int s1=0,d1=n-1,m1,s2=1,d2=n-1,m2, //分别表示序列A和B的首位数、末位数和中位数 while(s1!=d1||s2!=d2)( m1=(S1+d1)/2, m2=(s2+d2)/2; if(A[m1];==B[m2]) return A[m1],//满足条件1) if(A[m1]<B[m2]){//满足条件2) if((s1+d1)%2==0){//若元素个数为奇数 s1=m1;//舍弃A中间点以前的部分,且保留中间点 d2=m2;//舍弃B中间点以后的部分,且保留巾间点 } else f//元素个数为偶数 s1=m1+1;//舍弃A中间点及中间点以前部分 d2=m2;//舍弃B中间点以后部分且保留中间点 } } elsef//满足条件3) if((sl+d1)%2==0){//若元素个数为奇数 d1=m1,//舍弃A中间点以后的部分,且保留中间点 s2=m2;//舍弃B中间点以前的部分,且保留中间点 } else{//元素个数为偶数 d1=m1;//舍弃A中问点以后部分,且保留中间点 s2=m2+1;//舍弃B中间点及中间点以前部分 } } } return A[s1]<B[s2]?A[s1]:B[s2], }
解析
转载请注明原文地址:https://kaotiyun.com/show/sBRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
关于闭关政策的叙述中,不正确的是()。
胡适与李大钊进行“问题与主义之争”的主战场是()。
我国对外开放格局的形成过程。
以下关于阿兹特克文化的叙述,不正确的是()。
某新石噐遗址发现大量稻谷壳和稻草,红士,防洪水城垣,此遗址可能是
已知散列函数为H(key)=key%11,处理冲突的方法为二次探测法,探测的序列为:1,-1,4,-4,…,j2,-j2(j<=m/2)。当di>0时,Hi=(H(key)+di)%m当di<0时,Hi=(H(key)+di+m)%m散列
若二叉树的前序序列为DABCEFG,中序序列为BACDFGE,则其层次序列为()。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(e1,e2.…,em);i=l;while(所剩边数>=顶点数){从图中删去ei;若图不再连通,则恢复ei;i=i+l;
随机试题
我国社会主义改革的性质是( )
Inthecaseofmobilephones,changeiseverything.Recentresearchindicatesthatthemobilephoneischangingnotonlyourcul
羚羊角锉末服的用量
背景资料:某普通铁路桥梁工程,桥跨布置为12×32m简支T梁+(40+56+40)m连续箱粱+6×32m简支T梁;0号桥台采用C25混凝土扩大基础,基础尺寸为14.6m×10.6m,厚3.0m,其余墩台为钻孔桩基础。根据设计要求,由于0号桥台基础为大体积
期货价差套利的作用包括()。
甲公司计划贷款,期限为1年,银行要求按照贷款额的20%保持补偿性余额,同时采用贴现法付息。已知贷款年利率为5%,则该项贷款的有效年利率为()。
班主任在与小明谈话时说:“根据前段时间你的表现,虽然学习效果不很理想,但非常努力,如果注意改进学习方法,相信成绩会不断提高。”其中的评价属于()。
以下是某市110报警平台接警员接听的一段报警电话内容:接警员:“您好。这里是XX市110报警服务平台,我是XX号接警员。请讲。”报警人:“我家里进贼了!在撬我的房门!我在卧室里很害怕。你们赶紧来!”接警员:“请问您家的具体位置
英、红、燕三个人讨论一数学题,当她们都把自己的解法说出来以后,英说:“我做错了”。红说:“英做对了”。燕说:“我做错了”。老师看过她们的答案并听了她们的上述意见后说:“你们三个人有一个做对了,有一个说对了”。那么,谁做对了呢?
DoyoupreferwatchingsportonTVoronthescene?
最新回复
(
0
)