leetcode-practice-in-cpp/cpp/stack_queue/0295_find_median_from_data_stream/optimized.cpp at main · TTSS0529/leetcode-practice-in-cpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include "find_median_from_data_stream.hpp"

MedianFinder::MedianFinder() {
}

void MedianFinder::addNum(int num) {
    if (_maxHeap.empty() || num <= _maxHeap.top()) {
        _maxHeap.push(num);
    } else {
        _minHeap.push(num);
    }
    if ( _maxHeap.size() > _minHeap.size() + 1) {
        _minHeap.push(_maxHeap.top());
        _maxHeap.pop();
    } else if (_minHeap.size() > _maxHeap.size() + 1) {
        _maxHeap.push(_minHeap.top());
        _minHeap.pop();
    }
}

double MedianFinder::findMedian() {
    if (_maxHeap.size() == _minHeap.size()) {
        return (static_cast<double>(_maxHeap.top()) + _minHeap.top()) / 2.0;
    } else if (_maxHeap.size() > _minHeap.size()) {
        return static_cast<double>(_maxHeap.top());
    } else {
        return static_cast<double>(_minHeap.top());
    }
}