數(shù)據(jù)流中的中位數(shù)

題目描述

如何得到一個數(shù)據(jù)流中的中位數(shù)？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流，使用GetMedian()方法獲取當(dāng)前讀取數(shù)據(jù)的中位數(shù)。

學(xué)習(xí)了STL的push_heap和pop_heap操作, 傳送門

class Solution { public:void Insert(int num){if (((min.size() + max.size()) & 1) == 0) { // 偶數(shù), 應(yīng)該插入最小堆中if (max.size() > 0 && max[0] > num) { // 最大堆中的數(shù)字大于要插入的數(shù)字max.push_back(num);push_heap(max.begin(), max.end(), less<int>());num = max[0];pop_heap(max.begin(), max.end(), less<int>());max.pop_back();}min.push_back(num);push_heap(min.begin(), min.end(), greater<int>());}else { // 奇數(shù), 插入最大堆if (min.size() > 0 && min[0] < num) { // 最小堆小于這個數(shù)min.push_back(num);push_heap(min.begin(), min.end(), greater<int>());num = min[0];pop_heap(min.begin(), min.end(), greater<int>());min.pop_back();}max.push_back(num);push_heap(max.begin(), max.end(), less<int>());}}double GetMedian(){ int size = min.size() + max.size();if (0 == size)return 0;if ((size & 1) == 1)return min[0];else return (min[0] + max[0]) / 2.0;}private:vector<int> min;vector<int> max; };

優(yōu)先級隊列也遇到了

class Solution {priority_queue<int, vector<int>, less<int> > p;priority_queue<int, vector<int>, greater<int> > q;public:void Insert(int num){if(p.empty() || num <= p.top()) p.push(num);else q.push(num);if(p.size() == q.size() + 2) q.push(p.top()), p.pop();if(p.size() + 1 == q.size()) p.push(q.top()), q.pop();}double GetMedian(){ return p.size() == q.size() ? (p.top() + q.top()) / 2.0 : p.top();} };

轉(zhuǎn)載于:https://www.cnblogs.com/hesper/p/10564284.html

總結(jié)

以上是生活随笔為你收集整理的数据流中的中位数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。