首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
19
问题
一个长度为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
学硕统考专业
相关试题推荐
前期罗马帝国时期,关于罗马东方行省的传统手工业产品的叙述,不正确的是()。
(北魏孝文帝)“初谋南迁,恐众心恋旧,乃示为大举,因以胁定群情,外谋南伐,其实迁也。1日人怀土,多不所愿,内惮南征,无敢言者。于是定都洛阳。”上引材料不能说明的问题是()。
公元前1世纪,恺撒在征服高卢的过程中接触过一些西日耳曼人,并将见闻写成()。
论述世界反法西斯联盟的建立过程
试述欧洲中世纪的行会及其历史作用。
下列对第三次科技革命推动了国际经济格局调整的叙述,不正确的是()。
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
在一个双链表中,在*p结点之前插入*q结点的操作是()。
假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次,其中访问Cache缺失(未命中)50次,则Cache的命中率是()。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
随机试题
在Access中,匹配任意单字符的通配符是()
患者,女性,55岁。进行性吞咽困难半年余,经钡餐X线检查诊断为食管癌,拟行手术治疗。该患者术前护理措施错误的是
影响B型不良反应发生的因素有
6月中旬的一天中午饭后不久,某小学部分学生出现恶心、呕吐、腹痛、腹泻、头痛、心慌等症状,学校保健医生马上向卫生部门报告,食品卫生监督人员第一时间奔赴现场。经调查,发病的学生都与吃油炸豆角有关。专业人员一方面把中毒的学生紧急送往医院,另一方面对学生和家长进行
下列哪一情况不会引起嗜酸性粒细胞减少
根据《中华人民共和国反不正当竞争法》,不正当竞争行为是
A.做出明确的答复B.向消费者出具服务单据C.按约定履行,不得无理拒绝D.保证其与提供的商品的实际质量状况相符经营者提供的服务,按国家规定,承担包修、包换、包退责任的应()。
宽度为厚度的3倍或3倍以上的木材是()。
事故应急救援系统中的监测组织主要负责迅速测定事故的危害区域范围及危害性质,监测空气、水、食物、()的污染情况,以及气象监测等。
下列关于意外伤害保险的叙述不正确的是( )。
最新回复
(
0
)