一个长度为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个非负整数，数与数之间用空格间隔。
输出格式:
在一行内输出一个整数。
输入样例:
1. 6 2. 8 11 14 15 17 19 3. 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; }
