Fork me on GitHub

Find Median from Data Stream

Posted on

Description

https://leetcode.com/problems/find-median-from-data-stream/description/

Solution

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class MedianFinder {
private:
    vector<double> maxHeap;
    vector<double> minHeap;
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        int size = maxHeap.size() + minHeap.size();
        if (size & 1) {
            //Insert to minHeap;
            double maxItem = maxHeap[0];
            if (num >= maxItem) {
                minHeap.push_back(num);
                push_heap(minHeap.begin(), minHeap.end(), greater<double>());
            }else {
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(), maxHeap.end(), less<double>());
                minHeap.push_back(maxHeap[0]);
                pop_heap(maxHeap.begin(), maxHeap.end(), less<double>());
                maxHeap.pop_back();
                push_heap(minHeap.begin(), minHeap.end(), greater<double>());
            }
        }else {
            if (minHeap.empty() || num <= minHeap[0]) {
                maxHeap.push_back(num);
                push_heap(maxHeap.begin(), maxHeap.end(), less<double>());
            } else {
                minHeap.push_back(num);
                push_heap(minHeap.begin(), minHeap.end(), greater<double>());
                maxHeap.push_back(minHeap[0]);
                pop_heap(minHeap.begin(), minHeap.end(), greater<double>());
                minHeap.pop_back();
                push_heap(maxHeap.begin(), maxHeap.end(), less<double>());
                
            }
        }
    }
    
    double findMedian() {
        int size = maxHeap.size() + minHeap.size();
        return size & 1 ? maxHeap[0] : (minHeap[0] + maxHeap[0]) / 2.0; 
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */