My 184ms Solution with C++


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

Log in to reply
 

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