PTA甲级考试真题练习29——1029 Median
程序员文章站
2022-06-07 13:10:47
...
题目
思路
这题题意很简单,但是如果使用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;
}
推荐阅读
-
PTA甲级考试真题练习111——1111 Online Map
-
PTA甲级考试真题练习22——1022 Digital Library
-
PTA甲级考试真题练习18——1018 Public Bike Management
-
PTA甲级考试真题练习20——1020 Tree Traversals
-
PTA甲级考试真题练习30——1030 Travel Plan
-
PTA甲级考试真题练习17——1017 Queueing at Bank
-
PTA甲级考试真题练习8——1008 Elevator
-
PTA甲级考试真题练习23——1023 Have Fun with Numbers
-
PTA甲级考试真题练习5——1005 Spell It Right
-
PTA甲级考试真题练习11——1011 World Cup Betting