法一:用Multiset做的,因为它有个自动排序功能
class Solution { public: void Insert(int num) { stream.insert(num); } double GetMedian() { double res = 0.0; unsigned int size = stream.size(); multiset<int>::iterator it = stream.begin(); unsigned int cnt = size / 2; while(cnt){ --cnt; ++it; } if(size % 2 == 0) res = (double)(*it + *(--it)) / 2; else res = *it; return res; } private: multiset<int> stream; };
法二:用最大堆最小堆做
class Solution { private: int size = 0; priority_queue<int, vector<int>, less<int>> max; priority_queue<int, vector<int>, greater<int>> min; public: //用一个最大堆和一个最小堆做 void Insert(int num) { ++size; //偶数时,放入最小堆,奇数时,放入最大堆 //如果num为偶数,且比最小堆的top还大,则先入最小堆,再把堆顶入最大堆;num奇数同理 if(size & 1){ if(!min.empty() && num > min.top()){ min.push(num); num = min.top(); min.pop(); } max.push(num); } else{ if(!max.empty() && num < max.top()){ max.push(num); num = max.top(); max.pop(); } min.push(num); } } double GetMedian() { double res = 0.0; if(size == 0) return res; if(size & 1){ res = max.top(); } else{ res = (max.top() + min.top()) / 2.0; } return res; } };