首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
46
问题
一个长度为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的中位数。
要求:
给出算法的基本设计思想。
选项
答案
求两个序列A和B的中位数最简单的办法就是将两个升序序列进行归并排序,然后求其中位数。这种解法虽可求解,但在时间和空间两方面都不大符合高效的要求,但也能获得部分分值。 根据题目分析,分别求两个升序序列A和B的中位数,设为a和b。 ①若a=b,则a或b即为所求的中位数。 原因:容易验证,如果将两个序列归并排序,则最终序列中,排在子序列ab前边的元素为先前两个序列中排在a和b前边的元素;排在子序列ab后边的元素为先前两个序列中排在a和b后边的元素。所以子序列ab一定位于最终序列的中间,又因为a=b,显然a就是中位数。 ②否则(假设a<b),中位数只能出现(a,b)范围内。 原因:同样可以用归并排序后的序列来验证,归并排序后必然有形如…a…b…的序列出现,中位数必出现在(a,b)之间。因此可以做如下处理:舍弃a所在序列A的较小一半,同时舍弃b所在序列B的较大一半。在保留两个升序序列中求出新的中位数a和b,重复上述过程,直到两个序列中,只含一个元素时为止,则较小者即为所求的中位数。每次总的元素个数变为原来的一半。 算法的基本设计思想如下。 分别求出序列A和B的中位数,设为a和b,求序列A和B的中位数过程如下: ①若a=b,则a或b即为所求中位数,算法结束。 ②若a<b,则舍弃序列A中较小的一半,同时舍弃序列B中较大的一半,要求舍弃的长度相等。 ③若a>b,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求舍弃的长度相等。 在保留的两个升序序列中,重复过程①、②、③,直到两个序列中只含一个元素时为止,较小者即为所求的中位数。
解析
转载请注明原文地址:https://kaotiyun.com/show/oBRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
1824~1828年分别用不同的无机物通过不同的途径合成了同一种有机物——尿素,证明了化学定律对有机物和无机物是同样适用的科学家是()。
分析地理大发现在世界历史上的作用与地位。
下列不是苏俄实行战时共产主义政策原因的是()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
美国历史上第一个具有宪法性质的文件是()。
在下列查找的方法中,平均查找长度与结点个数n无关的查找方法是()。
在二叉树的顺序存储中,每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系,因此可与三叉链表对应。若某二叉树共有n个结点,采用三叉链表存储时,每个结点的数据域需要d个字节,每个指针域占用4个字节,若采用顺序存储,最后一个结点下标为k(起
某计算机采用二级页表的分页存储管理方式,按字节编址,页大小为2toB,页表项大小为2B,逻辑地址结构为:逻辑地址空间大小为216页,则表示整个逻辑地址空间的页目录表中包含表项的个数至少是____。
若无向图G=(V,E)中含有7个顶点,要保证图G在任何情况下都是连通的,则需要的边数最少是____。
随机试题
对于同种产品的进口,某国对一些国家实行高关税政策,而对另外一些国家实行低关税政策,这种做法不符合()
A.青蒿B.白薇C.胡黄连D.地骨皮E.银柴胡既退虚热,又利尿通淋的药是
关于药物相互作用A、作用相加或增加疗效B、保护药品免受破坏C、促进机体的利用D、延缓或降低抗药性E、增加毒性或药品不良反应苄丝肼或卡比多巴与左旋多巴合用
下列禁忌洗胃的药物中毒是
下列各项中,不属于应收管理模块初始化工作的是()。
在杜邦分析体系中计算权益乘数时,资产负债率是用期末负债总额与期末资产总额来计算的。()
材料二:1995年我国主要经济区生产力布局。由表格数据可以推断出()。
我国公务员职务共分()个序列。
犯罪中止:在犯罪过程中,自动放弃犯罪或者自动有效地防止犯罪结果发生的是犯罪中止。根据上述定义,下列不属于犯罪中止构成要件的是:
下列描述中错误的是
最新回复
(
0
)