计算机考研408真题2011年42题

题目来源： 计算机考研408真题2011年42题

题目描述：

• 描述: 42.（15分）一个长度为L（L≥1）的升序序列S.处在第「L/2]个位置的数称为S的中位数。例如，若序列S=（11,13，15，17，19），则S的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S=（2,4,6,8,20），则S和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。
  要求：
  1）给出算法的基本设计思想。
  2）根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释.
  3）说明你所设计算法的时间复杂度和空间复杂度。

思路1:

• 要注意"升序序列"、"等长"这两个信息,将题目的难度直接就降低了
  • 因为"升序序列",所以不需要我们自己进行排序
  • 因为"等长",假设长度为n,那么将A与B组成升序序列C后,C的长度为2n,中位数则是第n个数
• 所以将A和B序列从前到后依次取出每个元素进行比较,然后将较小的值给序列C
• 如果将A和B全部遍历后,得到C也是可以的,但是略微进行优化:对序列C的元素个数进行计数,当达到第n个元素,那么就停止对A和B的遍历,因为第n个元素就是所求的中位数

思路2:

• 因为思路1的时间和空间并不能算是高效,都是o(n)
• 根据题目,将序列A与B的中位数,设为a与b
  • 情况1.如果a=b,则a(或b)就是所求的中位数
  • 情况2.如果a<b,那么中位数只会出现在(a,b)的范围内
    • 那么舍弃a所在序列A的较小一半，同时舍弃b所在序列B的较大一半，在保留两个升序序列中求出新的中位数a和b，重复上述过程，直到两个序列中只含一个元素时为止，则较小者即为所求的中位数。
    • 每次总的元素个数变为原来的一半
      • a<b时，舍弃序列A中较小的一半，同时舍弃序列B中较大的一半，要求舍弃的长度相等。
      • a>b时，舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的长度相等。
  • 情况3.如果b<a,与2同理
• 代码中对于中间点的处理,其实就是为了两个序列舍弃的长度相等,如果a<b,可以将A序列和B序列进行归并排序后,得到最终序列…a…b…,可以通过这个模型进行逻辑上的理解,如果a<b,也是同理的

具体实现:

public class day408_11 {static int Search(int[] A, int[] B, int n){   //思路1的代码int[] C = new int[2*n];int i =0, j = 0,k = 0;while(k != n ){   //对序列C的元素个数进行计数,当达到第n个元素,那么就停止对A和B的遍历if(A[i]<B[j]){C[k++] = A[i++];}else if(A[i] == B[j]){C[k++] = A[i++];C[k++] = B[j++];}else{C[k++] = B[j++];}}return C[n-1];}static int Search1(int A[],int B[],int n){  //思路2的代码int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2; //s1指的是序列A的首位,也就是数组下标为0,s2同理//d1指的是序列A的末位,也就是数组下标为n-1,d2同理//m1指的是序列A的中位,m2同理while(s1 != d1||s2 != d2){m1 = (s1 + d1) / 2;m2 = (s2 + d2) / 2;if(A[m1] == B[m2])             //情况1.若A与B的中位数相等return A[m1];if(A[m1] < B[m2]){             //情况2.若A的中位数<B的中位数if((s1+d1) % 2 == 0){           //元素个数若为奇数:s1和d1都是下标,//所以元素个数如果是奇数,首尾下标相加是偶数s1 = m1;//舍弃A中间点以前的部分，且保留中间点d2 = m2;//舍弃B中间点以后的部分，且保留中间点}else{                          //元素个数若为偶数s1 = m1 + 1;//舍弃A中间点及中间点以前部分d2 = m2;//舍弃B中间点以后部分且保留中间点}}else{                          //情况3.若A的中位数>B的中位数if((s1+d1)%2 == 0){              //元素个数若为奇数 d1 = m1;//舍弃A中间点以后的部分，且保留中间点s2 = m2;//舍弃B中间点以前的部分，且保留中间点}else{                            //元素个数若为偶数d1 = m1 + 1;//舍弃A中间点以后部分，且保留中间点s2 = m2;//舍弃B中间点及中间点以前部分}}}return A[s1]<B[s2]?A[s1]:B[s2];}public static void main(String[] args) {int[] A = {1,2,3,4,5};int[] B = {6,7,8,9,10};System.out.println(Search(A,B,5));System.out.println(Search1(A,B,5));}
}

情感知识