首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
60
问题
一个长度为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
学硕统考专业
相关试题推荐
“二战”爆发的原因是多种因素综合作用的结果,其中最根本的因素是()。
论述斯巴达的阶级结构、政治制度和社会风尚
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
1217年,英格兰的《森林宪章》允许平民百姓在王室森林中放牧牲畜、挖掘水渠并从事其他农业活动。颁布该宪章的主要目的在于()
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
如图所示一台路由器连接3个以太网。请根据图中给出的参数回答如下问题:(1)该TCP/IP网络使用的是哪一类IP地址?(2)写出该网络划分子网后所采用的子网掩码。(3)系统管理员将计算机D和E按照图中所示结构连入网络并使用所分配的地址对TC
若一个栈的输入序列为1,2,3…n,输出序列的第一个元素是i,则第j个输出元素是()。
假定一台计算机的显示存储器用DRAM芯片实现,若要求显示分辨率为1600×1200,颜色深度为24位,帧频为85Hz,显存总带宽的50%用来刷新屏幕,则需要的显存总带宽至少约为____。
设有一个由正整数组成的无序(后向)单链表,编写能够完成下列功能的算法:(1)找出最小值结点,且打印该数值。(2)若该数值为奇数,则将其与直接后继结点的数值交换。(3)若该数值为偶数,则将其直接后继结点删除。
试述分页存储管理的基本实现原理,并说明如何实现从逻辑空间到物理空间的变换?
随机试题
可享受带薪年休假的有在_________。
在以下贸易术语中,术语后面加注的港口(地名)是目的港(目的地)的有()
患者突感胸闷、心前区痛,心电图显示室间隔前部心肌梗死。营养患处的动脉来自
A.输卵管妊娠B.生殖器结核C.盆腔炎性疾病D.卵巢上皮性癌E.子宫内膜异位症女,31岁。婚后2年未孕,性生活正常,既往痛经5年,妇科检查:子宫后倾后屈位,正常大小,活动度差,后穹隆有触痛结节,子宫左侧可触及直径5cm包块,该患者最可
下列有关法院审理反补贴案件的说法,哪些是错误的?()
某商品混凝土的目标产量是700m3,单价700元/m3,损耗率为4%;实际产量是650m3,单价为710元/m3,损耗率为3%。采用因素分析法进行分析,由于损耗率降低使成本减少了()元。
拥有丰富资源的股权投资基金,能够帮助被投资企业创造价值。以下对帮助被投资企业获得后续融资机会的描述,错误的是()。
A公司计划建设两条生产线,分两期进行,第一条生产线于2007年1月1日投资,投资合计为800万元,经营期限为10年,预计每年的税后经营现金流量为100万元;第二期项目计划于2010年1月1日投资,投资合计为l000万元,经营期限为8年,预计每年的税后经营现
学校教育是社会发展到一定_____阶段的产物。
Childrenhavebeensaidtohavebrain-injuredchildsyndrome,hyperactive(极度活跃的)childsyndromeandattention-deficitdisorder(AD
最新回复
(
0
)