首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
81
问题
一个长度为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
学硕统考专业
相关试题推荐
泰州学派源于王学、又不同于王学宗旨,是一个具有异端思想的思想学派,其代表人物是()
洋务运动的主要作用集中在()
为了确保西域通道,元封三年(前108),汉将()率轻骑击破楼兰,赵破奴率军击破姑师。
简述雅尔塔体系的内容和影响。
最早测量子午线的长度,并主持修订了当时最先进历法《大衍历》的是僧人()。
西北战场的关键一仗,由此,西北野战军由防御转入进攻,掌握了战争的主动权的战役是()
根据越南战争的起源和发展,分析“冷战”时期美国对第三世界政策的目标和动机。
设计一个算法求图的中心点。设v是有向图G的一个顶点,把v的偏心度定义为:MAX{从w到v的最短距离|w属于V(G))如果v是有向图G中具有的最小偏心度的顶点,则称顶点v是G的中心点。
[*]对应的微指令如下:ADD01XX1010000010XX10010000XX1001001001MOV00XX10100010XX1101001001
虚拟存储器技术是基于程序的()特性。
随机试题
Thereis________inthedirector’smostrecentfilmthatkeepsthemelodramaticpossibilitieslatentinitsscriptsafelyatbay.
试述人力资源战略的目标。
男性,50岁,从事机械修理30年,因咳嗽、活动时呼吸困难加剧,偶有局部一过性胸痛而就诊,X线胸片显示两侧肺野有较高密集度的不规则小阴影,纵隔胸膜增厚与心包粘连,心缘轮廓模糊不清,显示篷乱影像,临床医师要求劳动卫生职业病医师会诊。如果该病人尘肺诊断成立
以下对建设项目管理的工作内容描述正确的是()。
公路工程进度计划主要形式中,()主要是作为公路工程投标文件中施工组织设计的附表,以反映公路工程的施工进度。
某企业原有职工110人,其中技术人员是非技术人员的10倍,今年招聘后,两类人员的人数之比未变。且现有职工中技术人员比非技术人员多153人。问今年新招非技术人员多少人?
跨文化训练的目标不包括()。(中国传媒大学2011)
阅读以下叙述,回答问题【说明】J公司2008年3月中标某市公安局的人口管理系统开发项目,因该市要在2008年11月举办某大型国际会议,因此公安局要求人口管理系统一定要在2008年7月1日之前投入使用。强某是负责这个项目的项目经理,虽然他进
SDLC was invented by IBM to replace the older Bisynchronous protocol for wide area connections between IBM equipment. A varietio
A、Waitforthelecturetobegin.B、Goimmediatelytotheirseats.C、Getsomethingtodrinkfirst.D、Sitdownandenjoythelectu
最新回复
(
0
)