/*
* @lc app=leetcode id=295 lang=cpp
*
* [295] Find Median from Data Stream
*
* https://leetcode.com/problems/find-median-from-data-stream/description/
*
* algorithms
* Hard (38.20%)
* Likes: 1380
* Dislikes: 27
* Total Accepted: 125K
* Total Submissions: 326.7K
* Testcase Example: '["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]\n[[],[1],[2],[],[3],[]]'
*
* Median is the middle value in an ordered integer list. If the size of the
* list is even, there is no middle value. So the median is the mean of the two
* middle value.
* For example,
*
* [2,3,4], the median is 3
*
* [2,3], the median is (2 + 3) / 2 = 2.5
*
* Design a data structure that supports the following two operations:
*
*
* void addNum(int num) - Add a integer number from the data stream to the data
* structure.
* double findMedian() - Return the median of all elements so far.
*
*
*
*
* Example:
*
*
* addNum(1)
* addNum(2)
* findMedian() -> 1.5
* addNum(3)
* findMedian() -> 2
*
*
*
*
* Follow up:
*
*
* If all integer numbers from the stream are between 0 and 100, how would you
* optimize it?
* If 99% of all integer numbers from the stream are between 0 and 100, how
* would you optimize it?
*
*
*/
class MedianFinder {
private:
multiset<int> m;
multiset<int>::const_iterator l;
multiset<int>::const_iterator r;
public:
/** initialize your data structure here. */
MedianFinder() {
}
void addNum(int num) {
if (m.empty()) {
l = r = m.insert(num);
return;
}
m.insert(num);
const int N = m.size();
if (N & 1) {
// from even to odd
if (num >= *r) ++l;
else l = --r;
} else {
// from odd to even
if (num >= *r) ++r;
else --l;
}
}
double findMedian() {
return ((double)(*l) + (*r)) / 2;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/