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 | class MedianFinder {
private:
std::vector<int> v;
public:
void addNum(int num) {
auto it = std::lower_bound(v.begin(), v.end(), num);
v.insert(it, num);
}
double findMedian() {
int N = v.size();
if (N % 2 == 1)
return v[N / 2];
double left = v[N / 2];
double right = v[N / 2 - 1];
return (left + right) / 2.0;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
|