leetcode-sol/FindMedianFromDataStream.cpp at master · kohn/leetcode-sol · 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
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <string>
#include <vector>
#include <queue>
using namespace std;

// class MedianFinder {
// public:

//     vector<int> ds;
//     int size;

//     // Adds a number into the data structure.
//     void addNum(int num) {
// 	size++;
//         if(size == 1){
// 	    ds.push_back(num);
// 	} else{
// 	    if(num >= ds[ds.size()-1]){
// 		ds.push_back(num);
// 		return;
// 	    }

// 	    vector<int>::iterator iter = ds.begin();
// 	    int lo = 0;
// 	    int hi = ds.size()-1;
// 	    while(lo < hi){
// 		int mid = lo + (hi-lo)/2;
// 		iter =ds.begin() + mid;
// 		if(*iter < num && *(iter+1) >= num){
// 		    ds.insert(iter+1, num);
// 		    return;
// 		}
// 		else if(*iter >= num)
// 		    hi = mid;
// 		else
// 		    lo = mid;
// 	    }
// 	    if(lo == hi){
// 		iter = ds.begin()+hi;
// 		ds.insert(iter, num);
// 	    }
// 	}
//     }

//     // Returns the median of current data stream
//     double findMedian() {
// 	if(size%2==1){
// 	    return ds[ds.size()/2];
// 	} else{
// 	    return (ds[ds.size()/2-1] + ds[ds.size()/2])/2.0;
// 	}
//     }

//     void print(){
// 	for(int i:ds){
// 	    cout << i << " ";
// 	}
// 	cout << endl;
//     }

//     MedianFinder(){
// 	size = 0;
//     }
// };

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf;
// mf.addNum(1);
// mf.findMedian();

class MedianFinder {
public:

    priority_queue<int, vector<int>, greater<int> > larger;
    priority_queue<int, vector<int>, less<int> > smaller;
    int size;
    double median;

    // Adds a number into the data structure.
    void addNum(int num) {
	if(size == 0){
	    median = num;
	    smaller.push(num);
	    size++;
	} else{
	    size++;
	    if(num > median){
		larger.push(num);
	    } else if(num <= median){
		smaller.push(num);
	    }

	    if(larger.size() - smaller.size() == 2){
		smaller.push(larger.top());
		larger.pop();
	    } else if(smaller.size() - larger.size() == 2){
		larger.push(smaller.top());
		smaller.pop();
	    }

	    if(size & 1){
		median = larger.size()>smaller.size()?larger.top():smaller.top();
	    } else{
		median = (larger.top()+smaller.top())*0.5;
	    }
	}
    }

    // Returns the median of current data stream
    double findMedian() {
        return median;
    }
};

int main(int argc, char *argv[]) {
    MedianFinder mf;
    mf.addNum(6);
    cout << mf.findMedian() << endl;
    mf.addNum(10);
    //mf.print();
    cout << mf.findMedian() << endl;
    mf.addNum(2);
    //mf.print();
    cout << mf.findMedian() << endl;
    mf.addNum(6);
    //mf.print();
    cout << mf.findMedian() << endl;
    return 0;
}