两个序列的中位数(双指针)_双序列中位数

一个长度为n(n⩾1)的升序序列S,处在第2n​个位置的数称为序列S的中位数(median number),例如，序列S1={10,13,14,16,18,19}的中位数是14。两个序列的中位数是它们所有元素的升序序列的中位数，例如，S2={2,4,8,9,20,21},则S1和S2的中位数是13。现有两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列的中位数。

输入格式:

输入在三行进行，第一行1个非负整数N，表示两个数列的长度,第二行和第三行，每行N个非负整数，数与数之间用空格间隔。

输出格式:

在一行内输出一个整数。

输入样例:

6
8 11 14 15 17 19
2 4 6 9 10 12

输出样例:

10

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int n, x;
    vector<int>ans;
    
    scanf("%d", &n);
    for (int i = 0; i < 2 * n; i ++ )
    {
        scanf("%d", &x);
        ans.push_back(x);
    }
    int l1 = 0, l2 = n;
    for (int i = 1; i < n; i ++ )
    {
        if(ans[l1] < ans[l2]) l1 ++;
        else l2 ++;
    }
    if(ans[l1] < ans[l2]) printf("%d", ans[l1]);
    else printf("%d", ans[l2]);
    
    return 0;
}