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。
从此获得教训——以后程序运行结果出错时应先看大方向，把大方向弄无误了之后再去整理细节，否则就会犯钻牛角尖的错误。
转载于:https://www.cnblogs.com/Akatsuki-Sanjou/p/9785844.html
相关资源：JAVA上百实例源码以及开源项目