作者AstralBrain (妄想制御)
看板Prob_Solve
标题Re: online algorithm 找中位数
时间Sat Aug 18 21:13:30 2012
: 推 sorryChen:大神太强了..这样说起来需要O(mlogn)在n个+m个数,应该吧 08/18 12:13
: → singlovesong:只用一个平衡树应该也可以达到？ 08/18 15:18
只要满足两个条件的资料结构都可以:
1) insert一个数字 O(logn)
2) 找第k大的数 O(logn)
rb tree之类的平衡树都可以很简单的达成这个目标
zerojudge同一题, 改用rb tree写起来大概像这样
#include <cstdio>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
int main() {
int x;
tree<
pair<
int,
int>,
null_mapped_type,
less< pair<
int,
int> >,
rb_tree_tag,
tree_order_statistics_node_update
> t;
int n =
0;
while (scanf(
"%d", &x) !=
EOF) {
t.insert(make_pair(x, n++));
if (n %
2 ==
1) {
printf(
"%d\n", t.find_by_order(n /
2)->first);
}
else {
int median = (t.find_by_order(n /
2 -
1)->first
+ t.find_by_order(n /
2)->first) /
2;
printf(
"%d\n", median);
}
}
}
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 54.248.88.40
※ 编辑: AstralBrain 来自: 54.248.88.40 (08/18 21:16)
1F：推 sorryChen:谢谢大师用心指导 09/04 14:16