-
Notifications
You must be signed in to change notification settings - Fork 243
/
FindMedianFromDataStream.cpp
49 lines (43 loc) · 1.11 KB
/
FindMedianFromDataStream.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
// This is the solution for Find Median From Data Stream question from Leetcode
// https://leetcode.com/problems/find-median-from-data-stream/description/
class MedianFinder {
public:
priority_queue<int> max_heap;
priority_queue<int,vector<int>,greater<int>> min_heap;
MedianFinder() {
}
void addNum(int num) {
if(max_heap.size() > 0 && num > max_heap.top())
{
min_heap.push(num);
}
else
{
max_heap.push(num);
}
if(max_heap.size() > min_heap.size()+1)
{
min_heap.push(max_heap.top());
max_heap.pop();
}
if(min_heap.size() > max_heap.size()+1)
{
max_heap.push(min_heap.top());
min_heap.pop();
}
}
double findMedian() {
if(max_heap.size() == min_heap.size())
{
return (max_heap.top()+min_heap.top())/2.0;
}
if(max_heap.size() > min_heap.size())
{
return max_heap.top();
}
else
{
return min_heap.top();
}
}
};