C++ 140ms solution with two heaps, O(logn) to add, O(1) to find.


  • 0
    P
    class MedianFinder {
    private: 
        priority_queue<int,std::vector<int>, std::greater<int>> q1;//top is the smallest
        priority_queue<int> q2;//top is the greatest
    public:
    
        // Adds a number into the data structure.
        void addNum(int num) {//keep q2.size()>=q1.size()
            if(q2.empty()){
                q2.push(num);
                return;
            }
            if(num<=q2.top()){
                if(q2.size()<=q1.size()) q2.push(num);
                else{
                    q1.push(q2.top());
                    q2.pop();
                    q2.push(num);
                }
            } 
            else{
                if(q2.size()<=q1.size()){
                    if(num<=q1.top()) q2.push(num);
                    else{
                        q2.push(q1.top());
                        q1.pop();
                        q1.push(num);
                    }
                }
                else{
                    q1.push(num);
                }
            }
        }
    
        // Returns the median of current data stream
        double findMedian() {
            if(q1.size()==q2.size()) return (q1.top()+q2.top())/2.0;
            return double(q2.top());
        }
    };

Log in to reply
 

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