首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
28
问题
一个长度为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
学硕统考专业
相关试题推荐
重庆谈判的焦点问题是()
提出行星绕太阳运行为椭圆形轨道的天文学家是()。
代表商代制陶工艺最高水平的是采用高岭土烧制的()。
试结合新民主主义革命不同历史时期的历史实际,阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。
以下不是巴黎和会的主要议题的是()
下列选项中不属于《国际联盟盟约》内容的是()。
中国封建社会后期的第一个启蒙学派是由王艮开创的()。
在击溃国民党的全面进攻和重点进攻中,人民解放军的主要作战目标是()。
印加人记载事物使用的方法是()。
设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页(Page)数据存储空间,页的大小为1KB,操作系统采用固定分配局部置换策略为此进程分配4个页框(PageFrame)。在时刻260前的该进程访问情况见表B一2(访问位即使
随机试题
下列不属于Swing中构件的是()。
证券投资资金管理公司
下列血管炎中,属于肉芽肿性血管炎的是:
合伙人之间的关系是一种合同关系。()
商品流通企业的资源按其是否容易辨识和评估来划分,可以分为有形资源和无形资源。下列属于有形资源的有()。
某企业(位于市区)为增值税一般纳税人,增值税适用税率为17%,2006年企业全年实现销售收入总额9200万元,扣除的成本、费用、税金和损失总额9016万元,实现利润184万元。经聘请的会计师事务所审计,发现有关涉税问题如下:(1)12月将闲置多年
【《甘石墨经》】
April1DearValuedClient,WewouldliketoexpressourgratitudetoyouforrenewingyourInternetconnectionsubscriptionwit
AtachesstournamentinTunisiain1967,BobbyFischer,then24,waspittedagainstanotherAmericangrandmaster,SamuelReshe
Thetimeofyearababyisborncanshapewhatprofessiontheywillembarkoninlaterlife,anewresearchhassuggested.Being
最新回复
(
0
)