Time Cost

13min39s

Implementation

We built two heaps to represent all numbers. A min heap represents the larger half which includes [mid + 1, largest] elements. A max heap represents the smaller half which includes [smallest, mid]. In the case, if we could get numbers[mid+1] while minheap.top() meanwhile getting numbers[mid] while maxheap.top(). We then judge if the newly added num should be placed in which half.

Furthermore, we set a constraint on two heaps where minheap size always be (size+1)/2 which means sizeof(minheap) >= sizeof(maxheap). In this case, we can simply get the median value in different cases.

Code

• Solution

  class MedianFinder {
  public:
    int size;
    priority_queue<int, vector<int>, greater<int>> minheap; // largest -> mid + 1
    priority_queue<int> maxheap; // mid -> smallest
  
    // Make minheap size always (size+1)/2
  
    MedianFinder() {
        size = 0;
    }
      
    void addNum(int num) {
        if (size == 0) {
            minheap.emplace(num);
        }else if (size & 1) {
            if (num > minheap.top()) {
                maxheap.emplace(minheap.top());
                minheap.pop();
                minheap.emplace(num);
            }else{
                maxheap.emplace(num);
            }
        }else{
            if (num < maxheap.top()) {
                minheap.emplace(maxheap.top());
                maxheap.pop();
                maxheap.emplace(num);
            }else{
                minheap.emplace(num);
            }
        }
        size++;
    }
      
    double findMedian() {
        if (size & 1) {
            // size is odd
            return minheap.top();
        }
        double result = (minheap.top() + maxheap.top()) / 2.0;
        return result;
    }
  };