C++ solution using std::priority_queue


  • 0
    Y

    count here is used to record the number of elements.

    class MedianFinder {
    public:
        MedianFinder():count(0){}
        // Adds a number into the data structure.
        void addNum(int num) {
            if(count%2){
                //should push right
                if(num < leftMaxHeap.top()){
                    leftMaxHeap.push(num);
                    num = leftMaxHeap.top();
                    leftMaxHeap.pop();
                }
                rightMinHeap.push(num);
            }else{
                //should push left
                if(!rightMinHeap.empty() && num > rightMinHeap.top()){//should check if rightHeap is empty()
                    rightMinHeap.push(num);
                    num = rightMinHeap.top();
                    rightMinHeap.pop();
                }
                leftMaxHeap.push(num);
            }
            ++count;
        }
    
        // Returns the median of current data stream
        double findMedian() {
            if(count%2){
                return leftMaxHeap.top();
            }else{
                if(count == 0) return -1;//error, empty
                else return (double)leftMaxHeap.top()/2 + (double)rightMinHeap.top()/2;
            }
        }
        
    private:
        int count;
        priority_queue<int, vector<int>, greater<int>> rightMinHeap;
        priority_queue<int, vector<int>, less<int>> leftMaxHeap;
    };
    
    // Your MedianFinder object will be instantiated and called as such:
    // MedianFinder mf;
    // mf.addNum(1);
    // mf.findMedian();

Log in to reply
 

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