2. 考研
  3. 一个长度为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的中位数是

admin2015-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

学硕统考专业

相关试题推荐
随机试题
最新回复(0)