题解 | #Median#

#include <iostream>
#include <vector>
using namespace std;
vector<int> vec1;
vector<int> vec2;
int solution(int begin1,int end1,int begin2,int end2,int k){
    if(k==1) return min(vec1[begin1],vec2[begin2]);//找第一小的数字直接返回两个数组较小的那个值
    if(begin1>end1||begin2>end2){//有个数组已经遍历完，那么第k小的数字一定是在另一个数组第k位
        if(begin1>end1) return vec2[begin1+k-1];
        else return vec1[begin2+k-1];
    }
    int mid = k/2;//
    //小的一边的数组从begin位置开始到mid位置中必定没中位数，全部删掉，再递归找第k-mid小的数
    if(vec1[begin1+mid-1]<=vec2[begin2+mid-1]){
        return solution(begin1+mid,end1,begin2,end2,k-mid);
    }else{
        return solution(begin1,end1,begin2+mid,end2,k-mid);
    }
    return 0;
}   
int main() {
    int n,m;
    while (cin>>n) { // 注意 while 处理多个 case
        vec1.resize(n+1);
        for(int i=1;i<=n;i++) cin>>vec1[i];
        cin>>m;
        vec2.resize(m+1);
        for(int i=1;i<=m;i++) cin>>vec2[i];
        int k = (n+m+1)/2;//找第K小
        cout<<solution(1,n,1,m,k)<<endl;
    }
}
// 64 位输出请用 printf("%lld")