首页 26考研 在职考研 直播好课 大纲冲刺

新东方在线 > 考研 > 计算机 > 考研计算机真题 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

42.(15分)一个长度为L(L≥1)的升序序列S，处在第[L/2]个位置的

2021-07-06 07:02:00来源：新东方在线

　　【题目】

　　42.(15分)一个长度为L(L≥1)的升序序列S，处在第[L/2]个位置的数称为s的中位数。例如，若序列S1：(11，13，15，17，19)，则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则S1和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。

　　要求：

　　(1)给出算法的基本设计思想。

　　(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。

　　(3)说明你所设计算法的时间复杂度和空间复杂度。

　　【答案要点】：

　　(1)给出算法的基本设计思想：(5 分)

　　分别求两个升序序列A、B 的中位数，设为a 和b。若a=b，则a 或b 即为所求的中位数;否则，舍弃a、b 中较小者所在序列之较小一半，同时舍弃较大者所在序列之较大一半，要求两次舍弃的元素个数相同。在保留的两个升序序列中，重复上述过程，直到两个序列中均只含一个元素时为止，则较小者即为所求的中位数。

　　(2)算法实现：(8 分)

　　int M _ Search(int A[ ],int B[ ],int n){

　　int start1, end1, mid1, start2, end2, mid2 ;

　　start1 =0;end1 =n-1 ;

　　start2 = 0 ; end2 = n- 1 ;

　　while(start1 ! = end1 || start2 ! = end2)

　　{ mid1 = (start1 +end1 )/2 ;

　　mid2 = ( start2 +end2 )/2 ;

　　if(A[mid1 ] = =B[mid2]) return A[mid1 ] ;

　　if( A [ mid1 ]

　　{//分别考虑奇数和偶数，保持两个子数组元素个数相等

　　if((start1+end1)%2==0){//若元素为奇数个

　　start1=mid1; //舍弃A 中间点以前的部分且保留中间点

　　end2=mid2; //舍弃B 中间点以后的部分且保留中间点

　　}

　　else{ //若元素为偶数个

　　start1=mid1+1;//舍弃A 的前半部分

　　end2=mid2; //舍弃B 的后半部分

　　}

　　}

　　else{

　　if((start1+end1)%2=：0){//若元素为奇数个

　　end1=mid1; //舍弃A 中间点以后的部分且保留中间点

　　start2=mid2; //舍弃B 中间点以前的部分且保留中间点

　　}

　　else{//若元素为偶数个

　　end1=mid1; //舍弃A 的后半部分

　　start2=mid2+1;//舍弃B 的前半部分

　　}

　　}

　　}

　　return A[start1]

　　}

　　(3)上述所给算法的时间、空间复杂度分别是0(log2n)和0(1)。(2 分)


考研公开课小程序

本文关键字: 一个长度为L(L≥1)的升序序列S

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
看课程 MBA 优惠券 0元学 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

名师试听

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10