[PAT解题报告] Median
两个有序数组的中位数是个经典的问题，但是本题对时间要求不高，所以可以用归并排序的方法来做，所以就很简单了。归并排序找到第k个元素就可以了。时间复杂度是O(k)其中k是(na
+ nb) / 2。还有题目里说的long，我还是用了long long。
代码：
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
long long a[1000006], b[1000006];
int main() {
int na,nb;
scanf("%d",&na);
for (int i = 0; i < na; ++i) {
scanf("%lld",a + i);
}
scanf("%d", &nb);
for (int j = 0; j < nb; ++j) {
scanf("%lld", b + j);
}
for (int i = 0, j = 0, k = 0, c = 0,want = (na + nb - 1) >> 1; (i < na) || (j < nb); ++k) {
if (i >= na) {
c = 1;
}
else if (j >= nb) {
c = 0;
}
else {
c = (a[i] < b[j])?0:1;
}
if (c == 0) {
if (k == want) {
printf("%lld\n",a[i]);
break;
}
++i;
}
else {
if (k == want) {
printf("%lld\n",b[j]);
break;
}
++j;
}
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1029
投递科大讯飞等公司10个岗位 >