PAT——1029 Median (25 分)

题目大意:

给两个非递减序列,求它们合并后中位数。

题目解析:

一开始用两个数组存储序列,然后计算求中位数,结果发现超出内存限制。改为存储第一个序列,第二序列边读边求,通过。

具体代码:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 200005
int A[MAXN];
int B;
int main()
{
	int m,n,middle;
	int res;
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%d",&A[i]);
	}
	scanf("%d",&n);
	if((m+n)%2==0)
		middle=(m+n)/2;
	else
		middle=(m+n)/2+1;
	int k=0,i=0,j=0;
	scanf("%d",&B);
	while(i<m&&j<n&&k<middle){
		if(A[i]<B)
			res=A[i++];
		else{
			res=B;
			scanf("%d",&B);
			j++;
		}
		k++;
	}
	while(i<m&&k<middle){
		res=A[i++];
		k++;
	}
	while(j<m&&k<middle){
		res=B;
		scanf("%d",&B);
		j++;
		k++;
	}
	printf("%d",res);
    return 0;
}
全部评论

相关推荐

ZywOo_求职版:谁问你了....
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务