0%

LeetCode: Find Median from Data Stream

找中位数,用两个大根堆来记录按大小排列时中间的两个数

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
class MedianFinder {
public:

// Adds a number into the data structure.
void addNum(int num) {
small.push(num);
big.push(-small.top());
small.pop();
if(small.size()<big.size())
{
small.push(-big.top());
big.pop();
}
}

// Returns the median of current data stream
double findMedian() {
if(big.size()==small.size())
return small.top()-(big.top()+small.top())/2.0;
else
return small.top();
}

private:
priority_queue<int> small, big;
};

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