# 295. Find Median from Data Stream - CPP - Solution

• ``````// 295. Find Median from Data Stream
// https://leetcode.com/problems/find-median-from-data-stream/
#include <iostream>
#include <cassert>
#include <cmath>
#include <set>
#include <cfloat>
#include <algorithm>
#include <iterator>
using namespace std;
class MedianFinder {
public:

// Adds a number into the data structure.
void addNum(int num) {
if (minSet.empty() && maxSet.empty()) {
minSet.insert(num);
return;
}
if (minSet.size() < maxSet.size()) {
if (num <= *begin(maxSet)) {
minSet.insert(num);
return;
}
if (num > *begin(maxSet)) {
minSet.insert(*begin(maxSet));
maxSet.erase(begin(maxSet));
maxSet.insert(num);
return;
}
return;
}
if (minSet.size() > maxSet.size()) {
if (num >= *prev(end(minSet))) {
maxSet.insert(num);
return;
}
if (num < *prev(end(minSet))) {
maxSet.insert(*prev(end(minSet)));
minSet.erase(prev(end(minSet)));
minSet.insert(num);
return;
}
return;
}
if (minSet.size() == maxSet.size()) {
if (num <= *begin(maxSet)) {
minSet.insert(num);
return;
}
if (num > *begin(maxSet)) {
maxSet.insert(num);
return;
}
return;
}
return;
}

// Returns the median of current data stream
double findMedian() {
if (minSet.size() < maxSet.size()) {
return double(*begin(maxSet));
}
if (minSet.size() > maxSet.size()) {
return double(*prev(end(minSet)));
}
if (minSet.size() == maxSet.size()) {
double minSetMaxVal = double(*prev(end(minSet)));
double maxSetMinVal = double(*begin(maxSet));
return minSetMaxVal / 2.0 + maxSetMinVal / 2.0;
}
return 0.0;
}

private:
multiset<int> minSet;
multiset<int> maxSet;
};

// BEGIN: Time Limit Exceeded
// class MedianFinder {
// public:

// 	// Adds a number into the data structure.
// 	void addNum(int num) {
// 		rbtree.insert(num);
// 	}

// 	// Returns the median of current data stream
// 	double findMedian() {
// 		if (rbtree.size() & 1) {
// 			return *next(begin(rbtree), rbtree.size() >> 1);
// 		}
// 		double left = double(*next(begin(rbtree), (rbtree.size() >> 1) - 1));
// 		double right = double(*next(begin(rbtree), rbtree.size() >> 1));
// 		return left / 2.0 + right / 2.0;
// 	}

// private:
// 	multiset<int> rbtree;
// };
// END: Time Limit Exceeded

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.findMedian();

int main(void) {
MedianFinder mf;
double result = 0.0;

result = mf.findMedian();
assert(fabs(1.5 - result) < DBL_EPSILON);

result = mf.findMedian();
assert(fabs(2.0 - result) < DBL_EPSILON);

mf = MedianFinder();

result = mf.findMedian();
assert(fabs(6.0 - result) < DBL_EPSILON);

result = mf.findMedian();
assert(fabs(8.0 - result) < DBL_EPSILON);

result = mf.findMedian();
assert(fabs(6.0 - result) < DBL_EPSILON);

result = mf.findMedian();
assert(fabs(6.0 - result) < DBL_EPSILON);

result = mf.findMedian();
assert(fabs(6.0 - result) < DBL_EPSILON);

result = mf.findMedian();
assert(fabs(5.5 - result) < DBL_EPSILON);

result = mf.findMedian();
assert(fabs(6.0 - result) < DBL_EPSILON);

result = mf.findMedian();
assert(fabs(5.5 - result) < DBL_EPSILON);

result = mf.findMedian();
assert(fabs(5.0 - result) < DBL_EPSILON);

result = mf.findMedian();
assert(fabs(4.0 - result) < DBL_EPSILON);