# AC C++ solution, used two multiset

• ・Two `multiset` are used to sort the numbers.

・Data stream numbers are divided into these two `multiset`. `multiset 1` 's numbers are greater than `multiset 2` 's.

・Keep size of `multiset 1` is equal to size of `multiset 2` or equal to size of `multiset 2` +1.

``````class MedianFinder
{
private:
multiset<int> s1, s2;
public:

// Adds a number into the data structure.
{
int t;
multiset<int>::iterator it;
if (s1.empty() || n <= *s1.rbegin())
s1.insert(n);
else
s2.insert(n);
if (s1.size() > s2.size() + 1)
{
it = s1.end();
t = *(--it);
s1.erase(it); //t=*it need to be done before erase(it);
s2.insert(t);
}
else if (s2.size() > s1.size())
{
t = *s2.begin();
s2.erase(s2.begin());
s1.insert(t);
}
return;
}

// Returns the median of current data stream
double findMedian()
{
if (s1.size() > s2.size())
return (double)*s1.rbegin();
double d1, d2;
d1 = (double)*s1.rbegin();
d2 = (double)*s2.begin();
return (d1 + d2) / 2.0;
}
};
``````

After I watched discussions, there is a container whose name is priority_queue and can use negated numbers.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.