Interesting solution from @StefanPochmann


  • 0
    class MedianFinder {
        priority_queue<long> small, large;
        
    public:
    
        // Adds a number into the data structure.
        void addNum(int num) {
            small.push(num);
            large.push(-small.top());
            small.pop();
            if(small.size() < large.size()) {
                small.push(-large.top());
                large.pop();
            }
        }
    
        // Returns the median of current data stream
        double findMedian() {
            return small.size() > large.size() ? small.top() : (small.top() - large.top())/2.0;
        }
    };

Log in to reply
 

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