首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
75
问题
一个长度为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://www.kaotiyun.com/show/sBRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在1875年宪法中关于法国立法权的叙述,不正确的是()。
下列选项不属于封臣对封君义务的是()。
试结合新民主主义革命不同历史时期的历史实际,阐述中国共产党在处理同资产阶级复杂关系问题上的做法、结果及其历史经验。
中世纪战争史上有过两次君士坦丁堡陷落,分别简述其发生的时间、征战的双方、导致的历史变动。(华东师范大学2003年世界通史真题)
结合学界已有成果,评析李鸿章晚清外交活动。(北京大学2013年中国史真题)
下列事件:①上党战役②九三学社成立③“一二·一”惨案④《双十协定》签订,按照时间顺序排列正确的是()。
1920年,苏俄农民中流传着这样的说法:“土地属于我们,面包却属于你们;水属于我们,鱼却属于你们;森林属于我们,木材却属于你们”,它反映的是战时共产主义政策()。
简述按照恩格斯的划分方法人类的起源与进化。
十字军东征的目标是解放圣地()。
序列的“中值记录”指的是:如果将此序列排序后,它是第n/2个记录。试写出一个求中值记录的算法。
随机试题
PN结加反向电压时,空间电荷区将【】
以下哪项不是小儿年龄阶段的划分依据
男,18,右大腿下端肿胀,疼痛伴消瘦、乏力2个月。查体:右膝上肿胀,皮肤静脉怒张。X线片见右股骨下端骨质破坏,可见Codman三角。首先考虑的诊断是
张护士要给2床的患者输血1300ml。患者容易出现以下哪组电解质和酸碱平衡紊乱,张护士需注意观察
某建设项目废气中SO2的等标排放量是3.7×109,且该项目处于沿海地区,则该项目大气的评价等级为()。
会计法律制度是指国家权力机关和行政机关制定的各种会计规范文件的总称,下列各项中属于会计法律制度的有()。
阳慧在解决问题的过程中,常以老师、同学的建议作为参照做出决策。她的这种认知风格属于()。
某社区,实有人口2万余人,暂住人口1.8万余人,来自全国26个省市,房屋租赁市场管理混乱,治安隐患突出。几任社区民警都未能有效解决该问题。经验丰富的马某到该社区担任社区民警后,决心彻底扭转这种局面。他从警民关系入手,每天背着自制的音响设备,向群众宣传安全防
根据以下资料,回答问题。下列关于2009年各省区市普通高中招生数与专任教师数之比的描述,正确的是()。
人们预感失败不可避免时,积极地搜索乃至制造影响自己成功的不利因素,这种现象叫做()
最新回复
(
0
)