序列中位数

[编程题]序列中位数

热度指数：816 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知有整数数列a1,a2,a3,a4......an，数列中的整数的数量n为奇数；求数列中的中位数的数值。在求出中位数之后，如果持续的往原来的数列中添加整数（保证添加完成后数量仍为奇数），求出每次添加后新数列的中位数。

输入描述:

第一行代表原始数列，第一个数字为数列的数量n1，第二个数字开始为数列中的整数，一共n1个；

第二行开始是需要添加进数列的整数，该行第一个数字为添加的整数数量n2，第二个数字开始为添加到数列中的整数，一共n2个；

数列的最大数量不超过1,000,000万个

输出描述:

每行一个输出，表示当前整个序列的中位值

示例1

输入

3 100 20 1
2 30 100

输出

20
30

算法知识视频讲解

Adlexer Xu

发表于 2023-03-30 05:59:20

依题意，求一个动态变化的长序列中位数，即快速动态求中位数首先想到std::sort()，排序后输出序列中间位置的值即为中位数，显然对于n1长度的原始序列与n2长度的添加序列，有时间复杂度： O((n1+n2)log(n1+n2))O((n1+n2)log(n1+n2))O((n1+n2)log(n 展开全文