作者bleed1979 (十三)
站內Prob_Solve
標題Re: online algorithm 找中位數
時間Sat Aug 18 05:10:41 2012
※ 引述《sorryChen (陳揚和)》之銘言：
: ※ [本文轉錄自 Programming 看板 #1GBUF2_m ]
: 作者: sorryChen (陳揚和) 看板: Programming
: 標題: online algorithm 找中位數
: 時間: Fri Aug 17 14:25:04 2012
: 這是個面試問題..但我也不知道解答
: 給定一個一直會產生的數列..要如何最有效率的找到中位數
: 如果是要求平均只要constant time 和 space, 中位數就得要所有數都存了
: (因為任何過去出現的數都有可能在新產生幾個數列後變成中位數)
: 如果固定n個數, 需要O(n)的時間和空間可以找到第k大的數(任意k)
: (selection), 但如果這個數列一直在產生呢?
: 有沒有data structure 可以在n個數後新加m個數,而能在O(m)找到中位數?
: O(mlogn)倒是應該可以(不太確定)
: 若有個blance binary search tree, 並且計有每個子樹下有多少個數,
: 中位數應該離root不遠, 可能可以在有這樣的數中constant time找到
: (對嗎?) 新插入m個數也只要mlogn
: 實際問題若資料有特殊的分佈也許也可以把數分堆
: 不知道版上有沒有大師可以指導解惑
case 1:
n0, n1, n2, n3, n4, n5, n6, n7, n8, n9
=> priority_queue1 priority_queue2
n0, n1, n2, n3, n4 n5, n6, n7, n8, n9
midian = (n4 + n5) / 2
case 2:
n0
midian = n0
case 3:
n0, n1, n2
=> priority_queue1 priority_queue2
n0, n1 n2
midian = n1
http://zerojudge.tw/ShowProblem?problemid=d713
#include <iostream>
#include <queue>
using namespace std;
struct COMPL {
bool operator()(const int& lhs, const int& rhs) {
return lhs < rhs;
}
};
struct COMPR {
bool operator()(const int& lhs, const int& rhs) {
return lhs > rhs;
}
};
int n;
priority_queue<int, vector<int>, COMPL> qLeft;
priority_queue<int, vector<int>, COMPR> qRight;
int main() {
while(cin >> n) {
qLeft.push(n);
if(qRight.empty()) {
if(qLeft.size() > qRight.size() + 1) {
int tmp = qLeft.top();
qLeft.pop();
qRight.push(tmp);
cout << (qLeft.top() + qRight.top()) / 2 << "\n";
} else {
cout << qLeft.top() << "\n";
}
} else {
if(qLeft.size() > qRight.size() + 1) {
int tmp = qLeft.top();
qLeft.pop();
qRight.push(tmp);
cout << (qLeft.top() + qRight.top()) / 2 << "\n";
} else if(qLeft.top() > qRight.top()) {
int tmp = qLeft.top();
qLeft.pop();
qRight.push(tmp);
tmp = qRight.top();
qLeft.push(tmp);
qRight.pop();
cout << qLeft.top() << "\n";
} else {
cout << qLeft.top() << "\n";
}
}
}
return 0;
}
done.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.32.177.97
※ 編輯: bleed1979 來自: 114.32.177.97 (08/18 05:11)
1F：推 sorryChen:大神太強了..這樣說起來需要O(mlogn)在n個+m個數,應該吧 08/18 12:13
2F：→ singlovesong:只用一個平衡樹應該也可以達到？ 08/18 15:18
3F：推 eieio:我拿去問同事結果被秒殺，還問我怎麼會沒看過這題 orz 08/19 00:43