当前位置:首页 > 数据结构 > > 正文
SSOJ4174动态维护中位数
234+

题目大意:有n个数,请问前m个数的中位数是多少?多次询问哦!

题目描述

给出一个长度为N

的非负整数序列Ai,对于所有1k(N+1)/2,输出A1,A1A3,,A1A2k1的中位数。即前1,3,5,

个数的中位数。

输入

1

行为一个正整数N

,表示了序列长度。

2

行包含N个非负整数Ai(Ai109)

输出

(N+1)/2

行,第i行为A1,A3,,A2k1

的中位数。

样例输入

7
1 3 5 7 9 11 6

样例输出

1
3
5
6

提示

数据范围:10, 100, 1000, 5000, 8000, 10000, 20000, 30000, 50000, 70000, 100000

解题思路

动态维护中位数即可,对顶堆经典题目。

程序实现

暴力优化,二分查找、内存移动:动态维护有序数组,排好序后,中间那个数就是中位数。我们可以使用插入排序,先二分查找插入位置,再将大的元素往后移动一位,最后插入新的数字。

对顶堆:中位数m,左边的数字都不大于m,右边的数字都不小于m。只要发现左边的最大值大于右边的最小值,我们就可以将左边的元素,放到右边去。维护最大最小值,我们可以使用堆或者优先队列。对于新进来的数字,小的放左边,大的放右边,为了避免判空,先放左边,再移动到右边也行。接着维护数量,要求左边的不少于右边的,且至多比右边多1个。

SSOJ4174动态维护中位数:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter