My simple c++ solution using heap


  • 3
    K
    class MedianFinder {
    priority_queue<double, vector<double>, greater<double> >left;
    priority_queue<double, vector<double>, less<double> >right;
    double median=0;
    int diff=0;
    public:
    
    // Adds a number into the data structure.
    void addNum(int num) {
        diff=left.size()-right.size();
        num=double(num);
        if(diff==0){
            if(median < num){
                left.push(num);
                median=left.top();
            }
            else{
                right.push(num);
                median=right.top();
            }
        }
        else if(diff==1){
            if(median < num){
                right.push(left.top());
                left.pop();
                left.push(num);
            }
            else right.push(num);
            median= (left.top() + right.top() )/2;
        }
        else if(diff== -1){
            if(median < num)left.push(num);
            else{
                left.push(right.top());
                right.pop();
                right.push(num);
            }
            median=(left.top() + right.top() )/2;
        }
    }
    
    // Returns the median of current data stream
    double findMedian() {
        return median;
    }
    };

  • 0
    W

    share my easy code using two heaps and very easy to understand.
    MAXheap used to hold the half of less number,and minheap used to keep the other number.
    so ,according to the size of the two heaps .median element must be either the the top element of maxheap or minheap.code as follow.

    class MedianFinder {
    public:
    
    priority_queue<int,vector<int>,less<int>> maxh;
    priority_queue<int, vector<int>, greater<int>> minh;
    // Adds a number into the data structure.
    void addNum(int num) {
        maxh.push(num);
    	if (maxh.size() - minh.size() == 2)
    	{
    		minh.push(maxh.top());
    		maxh.pop();
    	}
        else if (minh.size()>0)
    	{
    		maxh.push(minh.top());
    		minh.pop();
    		minh.push(maxh.top());
    		maxh.pop();
    	}
    }
    
    // Returns the median of current data stream
    double findMedian() {
        if (maxh.size() == minh.size())
    	{
    		return (maxh.top()*1.0 + minh.top()*1.0) / 2;
    	}
    	else
    	{
    		return maxh.top();
    	}
    }
    

    };


Log in to reply
 

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