1. 实践题目 7-3 两个有序序列的中位数
2. 问题描述 已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,AN−1的中位数指A(N−1)/2的值,即第⌊(N 1)/2⌋个数(A0为第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 else 16 { 17 s3[k] = s2[j]; 18 k , j ; 19 } 20 } 21 while(i<N) //当s2指到结尾,s1未指到结尾时,继续遍历s1,将剩下的最小元素放入s3 22 { 23 s3[k] = s1[i]; 24 k , i ; 25 } 26 while(j<N) //当s1指到结尾,s2未指到结尾时,继续遍历s2,将剩下的最小元素放入s3 27 { 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./content-1-51951.html |
|