【实践】算法第二章上机实践报告

1. 实践题目

7-3 两个有序序列的中位数

 

2. 问题描述

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A​0​​,A​1​​,⋯,A​N−1​​的中位数指A​(N−1)/2​​的值,即第⌊(N 1)/2⌋个数（A​0​​为第1个数）。

Input

在一行中输出两个输入序列的并集序列的中位数。

Sample

输入1：

5

1 3 5 7 9

2 3 4 5 6

输出1：

4

输入2：

6

-100 -10 1 1 1 1

-50 0 2 3 4 5

输出2：

1

 

3. 算法描述

 1 #include <iostream> 2 using namespace std; 3 void Arrange(int s1[], int s2[], int N)　　//用于求两者并集，并输出结果的函数 4 { 5     int X = N   N; 6     int s3[X];　　　　　　　　　　//定义一个s3数组，存储两者的并集，空间大小为s1与s2数组大小之和 7     int i = 0, j = 0, k = 0;　 //定义三个指针，分别作为s1、s2、s3数组的指针 8     while(i<N && j<N)          //当s1、s2指针均没指到结尾时，遍历s1、s2，将每一步得到的最小元素放入s3中 9     {10         if(s1[i] < s2[j])11         {12             s3[k] = s1[i];13             k  , i  ;14         }15         else16         {17             s3[k] = s2[j];18             k  , j  ;19         }20     }21     while(i<N)　　　　　　　　　　//当s2指到结尾，s1未指到结尾时，继续遍历s1，将剩下的最小元素放入s322     {23             s3[k] = s1[i];24             k  , i  ;25     }26     while(j<N)                 //当s1指到结尾，s2未指到结尾时，继续遍历s2，将剩下的最小元素放入s327     {28             s3[k] = s2[j];29             k  , j  ;30     }31     cout << s3[(X-1)/2];　　   //在函数中输出s3的中位数32 }33 34 int main()35 {36     int N;37     cin >> N;38     int s1[N], s2[N];39     for(int i=0; i<N; i  )40     {41         cin >> s1[i];42     }43     for(int i=0; i<N; i  )44     {45         cin >> s2[i];46     }47     if( s1[(N-1)/2] == s2[(N-1)/2] )48     {49         cout << s1[(N-1)/2];50         return 0;51     }52     Arrange(s1, s2, N);53     return 0;54 }

 

4. 算法时间及空间复杂度分析

时间复杂度：

main()函数中有2个for循环，用于进行程序的输入，它们的时间复杂度均为O(n)，其余语句的时间复杂度均为O(1)；

Arrange(s1, s2, N)函数中，第一个while循环内嵌的是if和else条件判断语句，所以它的时间复杂度为O(n n)，即O(n)级别，剩余的两个while循环也同理。

因此，本算法的时间复杂度为O(n)。

空间复杂度：

因为变量只创建一次，且无需另外开辟辅助空间，因此，本算法的空间复杂度为O(1)。

 

5. 心得体会

写代码时要细心，写完之后要检查，运行结果出错时不要想当然。

若程序结果出错时，要先检查是否是算法大框架的问题。

本组在进行本程序的开发时，最初错将第10行的if(s1[i] < s2[j])错写为if(s1[i] < s2[i])，导致无法在所有情况下均获得Accepted结果。

在使用第一个Sample进行调试时，输出的是4而非5，我想当然以为排序出来的s3数组是正确的，产生问题的原因在于N为奇数，于是增加了奇数N情况下的条件判断，结果仍错误。

使用IDE进行调试过后，发现s3数组内部元素除了前几个以外其余的都是乱序，又增加了几个判断条件（也包括回溯指针等过程）均无法成功实行。

然后小组另一位成员提示：只需将i改为j即可成功，遂实行，结果为Accepted。

从此获得教训——以后程序运行结果出错时应先看大方向，把大方向弄无误了之后再去整理细节，否则就会犯钻牛角尖的错误。

来源：http://www.icode9.com/content-1-51951.html