首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
一个长度为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
45
问题
一个长度为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
学硕统考专业
相关试题推荐
明朝灭亡后,以下南明小朝廷存在的先后顺序是()。①绍武政权②永历政权③隆武政权④弘光政权
1837年倡导用无机肥料来补充土壤中耗去的化学元素的化学家是()。
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争,这一古老文件是()。
某系统中n个相互独立的生产者进程为一个消费者进程提供数据,假设每个生产者提供的数据写入各不相同的缓冲区,且生产者写缓冲区的速度比消费者读缓冲区的速度快,则缓冲区个数的最优值应为()。
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
若一个栈的输入序列为1,2,3…n,输出序列的第一个元素是i,则第j个输出元素是()。
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:求图G的关键路径,并计算该关键路径的长度。
一种数据编码的海明距是7,那么使用这种编码最多可以纠正()个错误。
16位真彩色显示器可显示的颜色种数为()。
试述CSMA/CD介质访问控制技术的工作原理。
随机试题
测定缓、控释制剂的体外释放度时,至少应测
对于肺虚咳嗽、肾虚作喘、虚劳喘咳之证可选用
《建设工程安全生产管理条例》规定,县级以上人民政府负有建设工程安全生产监督管理职责的部门在各自的职责范围内履行安全监督检查职责时,有权采取的措施有()。
“经营单位”栏应填:“保费”栏应填:
假设固定金额为100元,某投资者在2000点卖出一个单位上证指数,在1600点平仓,而交易保证金为10%,则该投资者的收益率为()
劳动争议仲裁委员会在依法处理劳动争议时,应遵循( )的效力高于行政法规效力的法律适用原则。
某公司是国内一家民营医药企业,为应对新产品上市导致的人员紧缺,在全国各地招聘了60名刚毕业的大学生。为了使这些新员工尽快适应工作,该公司人力资源部对这些新员工进行了为期一天的岗前培训,培训的内容以“任务与要求”、“权利与义务”为主,培训结束后还发给每人一本
虐待罪,是指对共同生活的家庭成员经常以打骂、捆绑、冻饿、限制自由、凌辱人格、不给治病或者强迫过度劳动等方法,从肉体上和精神上进行摧残迫害,情节恶劣的行为。根据定义,下列不构成虐待罪的是()。
(2012-上海-99)2010年,某新闻媒体披露,我国一些餐馆把“地沟油”作为餐饮用油,严重危害民众健康,于是各地相关部门根据媒体提供线索,开始进行查处封堵“地沟油”产业链的行动,地下作坊和违法企业被处罚或取缔。各地新闻媒体对行政部门的执法行动进行跟踪报
ROE[对外经济贸易大学2016金融硕士;中央财经大学2010研]
最新回复
(
0
)