【二路归并】中位数

题目

1506. 中位数 - AcWing题库

---

给定一个 $N$ 个整数构成的递增序列，中位数是中间位置的数字。

如果一共有奇数个数，则中位数是最中间的数；如果一共有偶数个数，则中位数是中间偏左的数。

例如 $S_1 = \lbrace 11,12,13,14 \rbrace$ 的中位数是 $12$ ， $S_2 = \lbrace 9, 10, 15, 16, 17 \rbrace$ 的中位数是 $15$ 。

两个序列的中位数定义为包含两个序列的所有元素的非递减序列的中位数。

例如， $S_1$ 和 $S_2$ 的中位数为 $13$ 。

给定两个递增序列，请你找出它们的中位数。

输入格式

共两行，每行包含一个递增序列。

每行首先包含一个整数 $N$ ，表示序列长度，接下来包含 $N$ 个整数，表示完整序列。

输出格式

输出一个整数，表示两个序列的中位数。

数据范围

$1 \le N \le 2 \times 10^5$ ,
序列中的整数都在 int 范围内。

输入样例：

4 11 12 13 14
5 9 10 15 16 17

输出样例：

13

解题

方法一：二路归并

思路

把两个有序数组做二路归并，然后取中位数即可。

代码

#include <iostream>

using namespace std;

const int N = 2e5 + 10;
int n, m;
int a[N], b[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 0; i < m; ++i) scanf("%d", &b[i]);
    int mid = n + m - 1 >> 1, i = 0, j = 0, curr;
    while ((i < n || j < m) && i + j <= mid) {
        if (i >= n) curr = b[j++];
        else if (j >= m) curr = a[i++];
        else if (a[i] < b[j]) curr = a[i++];
        else curr = b[j++];
    }
    printf("%d\n", curr);

    return 0;
}