-
Notifications
You must be signed in to change notification settings - Fork 3
/
MedianFinder.cpp
45 lines (39 loc) · 1.2 KB
/
MedianFinder.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
// #Hard #Top_100_Liked_Questions #Sorting #Two_Pointers #Design #Heap_Priority_Queue #Data_Stream
// #Big_O_Time_O(n*log_n)_Space_O(n) #2024_05_24_Time_231_ms_(98.67%)_Space_121.7_MB_(55.30%)
class MedianFinder {
public:
priority_queue<int> maxpq;
priority_queue<int, vector<int>, greater<int>> minpq;
MedianFinder() {
}
void addNum(int x) {
if (maxpq.empty() || maxpq.top() > x) {
maxpq.push(x);
} else {
minpq.push(x);
}
balanceHeaps();
}
void balanceHeaps(){
if (maxpq.size() > minpq.size() + 1) {
minpq.push(maxpq.top());
maxpq.pop();
} else if(minpq.size() > maxpq.size() + 1) {
maxpq.push(minpq.top());
minpq.pop();
}
}
double findMedian() {
if (maxpq.size() == minpq.size()) {
return (minpq.top() + maxpq.top()) / 2.0;
} else {
return (maxpq.size() > minpq.size())? (double) maxpq.top() : (double) minpq.top();
}
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/