首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
57
问题
一个长度为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
学硕统考专业
相关试题推荐
西汉前期诸侯国所拥有的权力中不包括()
结合学界已有成果,评析李鸿章晚清外交活动。(北京大学2013年中国史真题)
简述隋唐民族关系的特点、作用。
()是一部上起传说中的黄帝,下迄汉武帝时期的中国通史,是中国历史上第一部内容完整、结构周密的历史著作。
袁世凯得以复辟帝制不是因为()
光绪元年七月,清政府迫于()强烈要求派一位使臣到其国,()成为中国第一个驻外公使
西汉末年,()对太初历作了系统的解释,并调整为三统历。这是中国第一部记载完整的历法。
《马可波罗行纪》中载:“此汗八里大城之周围,约有城市二百,位置远近不等,每城皆有商人来此买卖货物,盖此城为商业繁荣之城也。”“此城”指的是()。
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
若无向图G=(V,E)中含有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是____。
随机试题
“这是多好的同志啊!”中的“啊”应读()。
引起细菌性肝脓肿最常见的原因是
关于SLE遗传基因的叙述,错误的说法是
甲胎蛋白(AFP)是何种癌的早期诊断重要指标
工程全部活动的顺序为( )。
越来越多的年轻观众对京剧缺乏了解,不懂得欣赏京剧的美;还有一部分人对舶来品,认为都比国内的好,对于自己国家的传统艺术,却认为是老土的、过时的东西,而__。依次填入画横线部分最恰当的一项是()。
CNSS是()的简称。
社会主义市场经济的基本框架包括()。
下列关于政权组织形式的表述,能够成立的有( )。
•Youwillhearfiveshortrecordings.Eachspeakerissayingwhatamanagermustdotoachievesuccess.•Foreachrecording,d
最新回复
(
0
)