-
Notifications
You must be signed in to change notification settings - Fork 11
/
Day-033.cpp
50 lines (45 loc) · 1.29 KB
/
Day-033.cpp
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
class MedianFinder {
priority_queue<int, vector<int>, greater<int>>mn; // min of greater values
priority_queue<int, vector<int>, less<int>>mx; // max of lesser values
public:
MedianFinder() {
}
void addNum(int num) {
if (mn.empty()) mn.push(num);
else if (mx.empty()){
if (mn.top() > num) {
mx.push(num);
} else {
mx.push(mn.top());
mn.pop();
mn.push(num);
}
}
else if (num < mx.top()) mx.push(num);
else mn.push(num);
if ((int)mx.size() -(int) mn.size() >= 2) {
mn.push(mx.top());
mx.pop();
} else if ((int)mn.size() -(int) mx.size() >=2) {
mx.push(mn.top());
mn.pop();
}
}
double findMedian() {
if ((mn.size() + mx.size())&1) {
if (mn.size() > mx.size()) {
return mn.top();
} else{
return mx.top();
}
} else {
return (mx.top() + mn.top())/2.0;
}
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/