PTA浙大版《数据结构学习与实验指导（第2版）》题目集----进阶实验1-3.1 两个有序序列的中位数

1.题目：

2.题目说明：

这道题，按照题目中的要求来看，应该是两个序列边合并边排序，成为一个非递减的序列。但是，我们在写的时候，很容易误解成合并后的序列S3是一个严格递增，即S1，S2中相同的元素在S3中只出现一次的序列。
我的想法很直接：边合并边排序。其他的思路是，直接动态申请初始化一个2*N长的数组，然后进行排序----希尔、快速排序等，但是冒泡排序会出现运行超时。

3.代码：（C语言）2020.11.15版

#include<stdio.h>
int a[100000],b[100000],c[200000];
/*写PTA时，大数组尽量定义在函数外*/
void middle( int N );
int main(){
	int N,i=0;
	scanf("%d",&N);
	for(i=0;i<N;i++) scanf("%d",&a[i]);
	for(i=0;i<N;i++) scanf("%d",&b[i]);
	if(N>0) middle( N );
	
	return 0;
	
}
void middle( int N ){
	int m=0,n=0,i=0,flag=1;
	while(flag){  /*flag用来控制是否应该接着合并*/
		flag=0;
		if(a[m]>b[n]){
			while(n<N&&a[m]>b[n]){
				c[i]=b[n];
				n++;
				i++;
				flag=1;
			}
		}
		if(a[m]<b[n]){
			while(m<N&&a[m]<b[n]){
				c[i]=a[m];
				m++;
				i++;
				flag=1;	
			}
		}
		if(a[m]==b[n]){
			while(n<N&&m<N&&a[m]==b[n]){
				c[i]=a[m];
				i++;
				c[i]=b[n];
				m++;
				n++;
				i++;
				flag=1;
			}
		} 
	} 
	/*处理剩余的元素*/
	while(m<N){
		c[i]=a[m];
		m++;
		i++;
	}
	while(n<N){
		c[i]=b[n];
		n++;
		i++;
	}
	m=i/2;
	n=i/2-1;
	if(i%2!=0) printf("%d",c[m]);
	else printf("%d",(c[m]+c[n])/2);
	
}

奥利给