Simple c++ 2 heap solution


  • 0
    W
    class MedianFinder {
    public:
    
        // Adds a number into the data structure.
        void addNum(int num) {
            _maxHeap.push(num);
            while (_minHeap.empty() || !_maxHeap.empty() && _minHeap.top() < _maxHeap.top()) {
                _minHeap.push(_maxHeap.top());
                _maxHeap.pop();
            }
            while (_minHeap.size() - 1 > _maxHeap.size()) {
                _maxHeap.push(_minHeap.top());
                _minHeap.pop();
            }
            while (_maxHeap.size() > _minHeap.size()) {
                _minHeap.push(_maxHeap.top());
                _maxHeap.pop();
            }
        }
    
        // Returns the median of current data stream
        double findMedian() {
            if (_minHeap.size() == _maxHeap.size()) {
                return static_cast<double>(_minHeap.top() + _maxHeap.top()) / 2.0;
            } else {
                return _minHeap.top();
            }
        }
    private:
        priority_queue<int, vector<int>, greater<int>> _minHeap;
        priority_queue<int> _maxHeap;
    };

Log in to reply
 

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