题意:
就给你一个无序的序列,问你中位数是什么
题解:
从内存限制可以看出来,这不是排个序就能解决的。
现在维护一个堆,这个堆有至少原序列一半的元素。现在采取这样的策略:
- 如果新进来的数字大于堆中的最大的数字,那么调整中位数的指针
- 如果新进来的数字在堆的区间内,那么把区间中最小的那个数给pop掉,并且把新来的数给push进去
那么最后就能得到一个把中位数覆盖的数列。
代码:
https://github.com/HarryGuo2012/ACMCode/blob/worldLine/URAL/1306.cpp