首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为L(L≥1)的升序序列s,处在第[L/2]个位置的数称为s的中位数。例如,若序列sl=(11,13,15,17,19),则s1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若s2=(2,4,6,8,20),则S1和s2
一个长度为L(L≥1)的升序序列s,处在第[L/2]个位置的数称为s的中位数。例如,若序列sl=(11,13,15,17,19),则s1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若s2=(2,4,6,8,20),则S1和s2
admin
2014-12-08
79
问题
一个长度为L(L≥1)的升序序列s,处在第[L/2]个位置的数称为s的中位数。例如,若序列sl=(11,13,15,17,19),则s1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数。例如,若s2=(2,4,6,8,20),则S1和s2的中位数是11。现在有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。要求:
给出算法的基本设计思想。
选项
答案
算法的基本设计思想如下。分别求出序列A和B的中位数,设为a和b,求序列A和B的中位数过程如下:①若a=b,则a或b即为所求中位数,算法结束。②若a
b,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求舍弃的长度相等。在保留的两个升序序列中,重复过程1)、2)、3),直到两个序列中只含一个元素时为止,较小者为所求的中位数。
解析
转载请注明原文地址:https://kaotiyun.com/show/q4xi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试析19世纪60年代列强对华政策的变化原因。(北京大学2006年中国通史真题)
论述安史之乱的原因与影响。
下列作品不属于明清时期地理学科代表作的是()
下列哪一项最符合《附益法》的主要内容?()
国民政府对日宣战的时间是()。
中国共产党在抗日民主根据地实行的土地政策是()。
下列选项中,不是由晁错提出的是()
西南军阀跟随孙中山拥护护法运动的目的是()。
下列城市:①南京②厦门③天津④杭州,按其在近代历史上开放为商埠的时间先后顺序排列应该是()
“二战”期间,美国研制了原子弹并用于实践;1946年美国投入使用的第一台电子计算机最初是用于计算炮弹弹道的;德国人研制成功的远程液体火箭是用于空袭英国的。以上史实说明()。
随机试题
与报纸产量有关的统计指标的基本单位是【】
简述国家和国际组织成为国际经济关系主体的过程。
意志行动过程可分为_______、_______两个阶段。
地方各级人大主要以召开会议的方式进行工作。会议每年至少举行一次,经下列选项中的哪一法定数额代表的提议可以临时召集本级人大会议?()
背景资料(二):下图所示为梁的结构施工图,请据图回答下列问题。该梁为框架梁,编号为7,共3跨。()
参加房地产经纪人资格全部4个科目考试的人员,必须在()考试年度内通过应试科目,才视为考试通过。
1994年提出的房改的内容可以概括为“三改四建”。下列对其表述有误的是()。
某工程双代号网络计划如下图所示,图中已标出各项工作的最早开始时间和最迟开始时间,该计划表明()。
连杆机构按各构件相对运动的性质不同,可分为()。
明治维新:睦仁天皇
最新回复
(
0
)