侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【二路归并】中位数

GabrielxD
2022-12-31 / 0 评论 / 0 点赞 / 145 阅读 / 502 字
温馨提示:
本文最后更新于 2022-12-31,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1506. 中位数 - AcWing题库


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

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

例如 S1={11,12,13,14}S_1 = \lbrace 11,12,13,14 \rbrace 的中位数是 1212S2={9,10,15,16,17}S_2 = \lbrace 9, 10, 15, 16, 17 \rbrace 的中位数是 1515

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

例如, S1S_1S2S_2 的中位数为 1313

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

输入格式

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

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

输出格式

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

数据范围

1N2×1051 \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;
}
0

评论区