首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
62
问题
一个长度为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的中位数。
要求:
说明你所设计算法的时间复杂度和空间复杂度。
选项
答案
算法的时间复杂度为O(log
2
n),空间复杂度为O(1)。
解析
综合考查了顺序表的折半查找和归并的思想。
转载请注明原文地址:https://kaotiyun.com/show/zBRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
以下关于玛雅文明叙述,不正确的是()。
西汉初年,反驳刘邦“马上治天下”的说法,并向汉帝国治国献策的是()。
简述地理大发现对欧洲经济、政治发展的影响,及其对世界整体化启动的作用。
毛泽东在《论持久战》中指出,中国抗日战争取得最后胜利最为关键的阶段是()。
西汉末年,()对太初历作了系统的解释,并调整为三统历。这是中国第一部记载完整的历法。
二战期间,下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役
三个进程P1、P2、P3互斥使用一个包含N(N>O)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用getev
设备管理中,设备映射表(DMT)的作用是()。
若无向图G=(V,E)中含有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是____。
在下列代码中,有3个进程P1、P2和P3,它们使用了字符输出函数putc来进行输出(每次输出一个字符),并使用了两个信号量L和R来进行进程间的同步。请问:当这组进程在运行的时候,在何种情形下,打印出来的字符“A”的个数是最少的,最少的个数是多少?
随机试题
A.平对第2胸椎棘突,相当于第2肋B.平对第3胸椎棘突,相当于第3肋C.平对第6胸椎棘突,相当于第6肋D.平对第7胸椎棘突,相当于第7肋E.平对第9胸椎棘突,相当于第9肋肩胛骨下角
教育心理学最核心的内容是()。
________是在流通领域专门从事商品买卖,以获取剩余价值为目的的________。 ________是商业资本家投资于商业经营活动所获得的利润。 商业利润的本质就是________,体现了商业资本家和产业资本家共同剥削雇佣工人的关系。
"经行吐衄"的发病机制主要是
患儿,男,10个月。反复肺炎2次。查体:体重7kg,心前区隆起,胸骨左缘第3~4肋间可闻及4/6级粗糙的全收缩期杂音,传导广泛,可触及震颤,肺动脉瓣第二心音亢进。最可能的诊断是
《招标投标法》规定,投标人递送投标文件的方式是()。
函数y=f(x)在点x=x2处取得极小值,则必有()。
根据钢材所含化学成分,钢材可分为()。
在类的定义中,用于为对象分配内存空间,对类的数据成员进行初始化并执行其他内部管理操作的函数是
Weweretoldthatwecouldnotswimuntil______cameinbecausetheseawastoofarout.
最新回复
(
0
)