首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
47
问题
一个长度为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
学硕统考专业
相关试题推荐
对三国鼎立到隋朝重新统一全国这段历史时期的政局,叙述正确的是()。①只有西晋有过短暂的统一②大多数时间是多个政权分立、南北对峙的复杂政局③西晋、北魏、东晋都有过短暂的统一④除三国分立以外,其他时间基本上处于统
中共十六届五中全会提出,建设社会主义新农村的要求是生产发展和()。
赫尔岑和车尔尼雪夫斯基是()的杰出代表人物。
评述戈尔巴乔夫外交“新思维”的实践活动及其影响。
19世纪末中国维新变法思想的基本内容是什么?与18世纪法国启蒙思想相比,两者在促进社会变革的作用上有何不同?为什么?
美国历史上第一个具有宪法性质的文件是()。
一棵:BS’r树共7个结点,值分别为1、2、3、4、5、6、7,形态为满二叉树,()不是插入序列。
已知在二叉树中,T为根结点,*p和*q为二叉树中两个结点,试编写求距离它们最近的共同祖先的算法。
在下列代码中,有3个进程P1、P2和P3,它们使用了字符输出函数putc来进行输出(每次输出一个字符),并使用了两个信号量L和R来进行进程间的同步。请问:当这组进程在运行的时候,在何种情形下,打印出来的字符“A”的个数是最少的,最少的个数是多少?
随机试题
提托穴的定位是()。
患者,女性,39岁,近半年来,每于感染或劳累后出现劳力性呼吸困难,并逐渐加重,休息后也不易缓解,一周前受凉后出现呼吸困难,伴咳嗽,咳大量泡沫样痰,夜间不能平卧,以“慢性心功能不全,二尖瓣狭窄”收入院。患者既往曾有反复链球菌性咽炎史。该患者心脏瓣膜病最可
月经周期的长短取决于下列何项因素
具有抗尿崩症作用的药物是
基金收益扣除按照国家规定可以扣除的费用等项目后的余额称为()。
某市区酒厂为增值税一般纳税人,2019年10月发生如下经济业务:(1)向某商场销售自产粮食白酒15吨,每吨不含税单价为80000元,收取包装物押金174000元,收取品牌使用费18100元。(2)从云南某酒厂购进粮食白酒6吨,专用发票上注明每吨不含税进
【2014广西】研究性学习既是一门课程,又是一种学习方式。()
LSAT
Inadditiontourgetoconformwhichwegenerateourselves,thereistheexternalpressureofthevariousformalandinformalgr
Itisnotpolitetoarriveatadinnerpartymorethan15to20minuteslate.Thehostorhostessusuallywaitsforallthegues
最新回复
(
0
)