295. Find Median from Data Stream

/** * 维护两个堆，可以用priority_queue, multiset * 大顶堆维护小的数值 * 小顶堆维护大的数值 */ class MedianFinder { private: priority_queue<int, vector<int>, less<int> > mn; priority_queue<int, vector<int>, greater<int> > mx; public: MedianFinder() { } void addNum(int num) { if (mn.empty() || mn.top() > num) { mn.push(num); if (mn.size() == mx.size() + 2) { int cur = mn.top(); mn.pop(); mx.push(cur); } } else { mx.push(num); if (mx.size() == mn.size() + 1) { int cur = mx.top(); mx.pop(); mn.push(cur); } } } double findMedian() { int size = mx.size() + mn.size(); if (size & 1) { return mn.top(); } else return (mn.top() + mx.top()) * 0.5; } };