Simple solution based on priority_queue in C++


  • 0
    C
    class MedianFinder {
    public:
        // Adds a number into the data structure.
        void addNum(int num) {
            if (maximal.size() <= minimal.size()) {
                minimal.push(num);
                maximal.push(minimal.top());
                minimal.pop();
            } else {
                maximal.push(num);
                minimal.push(maximal.top());
                maximal.pop();
            }
        }
    
        // Returns the median of current data stream
        double findMedian() {
            if (maximal.size() > minimal.size())
                return maximal.top();
            else
                return 0.5 * (minimal.top() + maximal.top());
        }
        
    private:
        priority_queue<int> maximal;
        priority_queue<int, vector<int>, greater<int>> minimal;
    };

Log in to reply
 

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