首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
58
问题
一个长度为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
学硕统考专业
相关试题推荐
在1875年宪法中关于法国立法权的叙述,不正确的是()。
张居正调抗倭名将()镇守蓟门,对安定北方人民的生活和保障社会生产的发展起了积极作用。
明朝在防御蒙古贵族方面采取了哪些重大措施?其代价和影响如何?
“改土归流”政策的根本目的是()。
阅读下列材料,回答问题:材料一:列宁说:“我们在夺取政权时便知道,不存在将资本主义制度具体改造成社会主义制度的现存方法……我不知道哪位社会主义者处理过这类问题……我们必须根据实践作出判断。”——摘自《苏联
下列法律文件中,规定内阁对君主负责的是()。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
带权图(权值非负,表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:①设最短路径初始时仅包含初始顶点,令当前顶点u为初始顶点;②选择离u最近且尚未在最短路
设有一个双向链表h,每个结点中除有prior,data和next三个域外,还有一个访问频度域freq,在链表被起用之前,每个结点中的freq域都被初始化为零。每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域中的值加一,并调整表中
如果一个没有内存映射的IO设备与主存之间交换数据,希望这种数据交换不经过CPU来完成,那么,可以采用的方法是()。
随机试题
关于有效焦点大小的叙述,错误的是
肱骨外科颈骨折,正确的摄影体位是
A.大黄B.芦荟C.番泻叶D.甘遂E.大戟治疗烧烫伤,应选用()
(2010年)Windows的设备管理功能部分支持即插即用功能,下面四条后继说明中有错误的一条是()。
案例一背景:某一级资质装饰施工队承接了一大厦南面石材及北面玻璃幕墙的安装工作。在进行石材幕墙施工中,由于硅酮耐候密封胶库存不够,操作人员为了不延误工期及时采用了不同于硅酮结构胶的另一品牌,事后提供了强度试验报告,证明其性能指标满足了承载力的要求。9
某公司有一台设备甲购于三年前,原值为60000元,预计净残值率10%,规定的使用年限为6年,采用平均年限法提取折旧,从目前的情况看至少还能使用4年。现在公司考虑是否更新该设备,新设备乙原值为50000元,预计净残值率为10%,规定使用年限为4年,采用年数总
利润是收入弥补成本费用后的余额,下列关于利润的说法中,不正确的是()。
皮亚杰认为,认知的本质是()。
根据以下资料。回答下列题。2011年1—11月,北京市规模以上工业经济效益综合指数为247.4,比上年同期提高4.2个百分点。实现利税1506.6亿元.比上年同期增长5.6%。2011年1—11月,规模以上工业企业实现利润931.5亿元
"Nomanisanisland,"wrotethepoetJohnDonneseveralcenturiesago.Hewas【C1】______oneofourmostdistinctive【C2】______:t
最新回复
(
0
)