题目描述
如何得到一个数据流中的中位数?
如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
样例
输入:1, 2, 3, 4
输出:1,1.5,2,2.5
解释:每当数据流读入一个数据,就进行一次判断并输出当前的中位数。
思路
算法实现时,一个蛮重要的点在每次都要往某一个某一个堆中添加元素(即使不应该插入,也要先插入另一个,再移动元素过去)。
按照刚才提到的步骤来操作,可以大幅减少过多的分支判断,让你的思路更加清晰。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| class Solution { public: priority_queue<int, vector<int>, less<int>> sh; priority_queue<int, vector<int>, greater<int>> bh; void insert(int num){ if (bh.empty() || num > bh.top()) { bh.push(num); } else { sh.push(num); bh.push(sh.top()); sh.pop(); } if (bh.size() == sh.size() + 2) { sh.push(bh.top()); bh.pop(); } }
double getMedian(){ if ((bh.size() + sh.size()) & 1) { return bh.top(); } else { return (bh.top() + sh.top()) / 2.0; } } };
|