欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA甲级考试真题练习29——1029 Median

程序员文章站 2022-06-07 13:10:47
...

题目

PTA甲级考试真题练习29——1029 Median

思路

这题题意很简单,但是如果使用merge对两个序列合并,或者是第二个序列逐个插入序列1中再输出中位数都会超时
这时应该思考,它只是让我们输出中位数,不用遍历整个数组,我们使用two pointer归并排序的思想,用ans记录每次比较后的最小值,再用cnt记录比较次数,如果到达中位数就可以直接输出了

代码

#include <iostream>
#include <string>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<list>
#include<sstream>
#include<string.h>
#include<math.h>
using namespace std;
#define nmax 105
#define inf 999999
vector<long> vec1;
vector<long> vec2;
int main()
{
	long num;
	cin >> num;
	for (int i = 0; i < num; ++i){
		long tmp;
		cin >> tmp;
		vec1.push_back(tmp);
	}
	cin >> num;
	for (int i = 0; i < num; ++i){
		long tmp;
		cin >> tmp;
		vec2.push_back(tmp);
	}
	int target = ceil((double)(vec1.size()+vec2.size()) / 2) - 1;
	int i = 0, j = 0;
	int vsize1 = vec1.size();
	int vsize2 = vec2.size();
	long ans = 0, cnt = 0;
	while (i < vsize1 && j < vsize2){
		ans = vec1[i] < vec2[j] ? vec1[i++] : vec2[j++];
		if (cnt++ == target){
			cout << ans;
			return 0;
		}
	}
	while(i<vsize1){
		ans = vec1[i++];
		if (cnt++ == target){
			cout << ans;
			return 0;
		}
	}
	while (j < vsize2){
		ans = vec2[j++];
		if (cnt++ == target){
			cout << ans;
			return 0;
		}
	}
	return 0;
}