题目
题目大意
给定两个递增序列,求这两个序列合并为一个递增序列后的中位数。
思路
直接用一个数组接收两个数组的输入,然后用sort()暴力求解,也可以过,但是时间复杂度较高。
更好的方法是双指针法,两个数组各一个指针来依次遍历,用一个count计数是否遍历到了中间位置,注意奇数个和偶数个的中间位置不一样。统一起来的表达式就是 (n1 + n2) / 2 + (n1 + n2) % 2 - 1。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
long long n1, n2;
cin >> n1;
vector<long long> v1(n1);
for (long long i = 0; i < n1; i++){
cin >> v1[i];
}
cin >> n2;
vector<long long> v2(n2);
for (long long i = 0; i < n2; i++){
cin >> v2[i];
}
long long i = 0, j = 0, m, mpos, count = 0;
mpos = (n1 + n2) / 2 + (n1 + n2) % 2 - 1; // 如果是偶数,/2后-1,如果奇数,/2
while (i < n1 && j < n2 && count <= mpos){
if (v1[i] < v2[j]){
m = v1[i];
i++;
}else{
m = v2[j];
j++;
}
count++;
}
while (i < n1 && count <= mpos){
m = v1[i];
i++;
count++;
}
while(j < n2 && count <= mpos){
m = v2[j];
j++;
count++;
}
cout << m << endl;
return 0;
} // 双指针法