Re: online algorithm 找中位數
看板Prob_Solve (計算數學 Problem Solving)作者AstralBrain (妄想制御)時間12年前 (2012/08/18 21:13)推噓1(1推 0噓 0→)留言1則, 1人參與討論串3/3 (看更多)
: 推 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)
推
09/04 14:16, , 1F
09/04 14:16, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
