首页 > 代码库 > 《Cracking the Coding Interview》——第18章:难题——题目9
《Cracking the Coding Interview》——第18章:难题——题目9
2014-04-29 04:18
题目:有一连串的数被读入,设计一个数据结构,能随时返回当前所有数的中位数。
解法:用一个大顶堆,一个小顶堆将数分成数量最接近的两份,就能轻松得到中位数了。
代码:
1 // 18.9 A stream of integers are passed to you, you have to tell me the median as they keep coming in. 2 #include <climits> 3 #include <iostream> 4 #include <vector> 5 #include <queue> 6 using namespace std; 7 8 template <class T> 9 struct LessFunctor 10 { 11 bool operator() (const T &x, const T &y) 12 { 13 return x < y; 14 } 15 }; 16 17 template <class T> 18 struct GreaterFunctor 19 { 20 bool operator() (const T &x, const T &y) 21 { 22 return x > y; 23 } 24 }; 25 26 template <class T> 27 class MedianArray { 28 public: 29 MedianArray() { 30 n_small = 0; 31 n_great = 0; 32 }; 33 34 void push(const T& val) { 35 if (n_great == 0) { 36 greater_heap.push(val); 37 ++n_great; 38 return; 39 } 40 41 if (n_great > n_small) { 42 smaller_heap.push(val); 43 ++n_small; 44 } else { 45 greater_heap.push(val); 46 ++n_great; 47 } 48 49 if (greater_heap.top() < smaller_heap.top()) { 50 T tmp; 51 52 tmp = greater_heap.top(); 53 greater_heap.pop(); 54 greater_heap.push(smaller_heap.top()); 55 smaller_heap.pop(); 56 smaller_heap.push(tmp); 57 } 58 }; 59 60 T median() { 61 if (n_great == 0) { 62 return INT_MIN; 63 } else if (n_great > n_small) { 64 return greater_heap.top(); 65 } else { 66 return (smaller_heap.top() + greater_heap.top()) / 2; 67 } 68 }; 69 70 ~MedianArray() { 71 n_small = 0; 72 n_great = 0; 73 while (!greater_heap.empty()) { 74 greater_heap.pop(); 75 } 76 while (!smaller_heap.empty()) { 77 smaller_heap.pop(); 78 } 79 }; 80 private: 81 int n_small; 82 83 // greater elements are stored in here. 84 priority_queue<T, vector<T>, GreaterFunctor<T> > greater_heap; 85 86 int n_great; 87 88 // smaller elements are stored in here. 89 priority_queue<T, vector<T>, LessFunctor<T> > smaller_heap; 90 }; 91 92 int main() 93 { 94 MedianArray<int> ma; 95 int val; 96 97 while (cin >> val) { 98 ma.push(val); 99 cout << ma.median() << endl; 100 } 101 102 return 0; 103 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。