AC C++ solution, used two multiset


  • 0

    ・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.
    	void addNum(int n) 
    	{
    		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.


Log in to reply
 

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