PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: online algorithm 找中位數

看板Prob_Solve (計算數學 Problem Solving)作者bleed1979 (十三)時間12年前 (2012/08/18 05:10)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串2/3 (看更多)

※ 引述《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)