Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class MedianFinder {
- priority_queue<int> left;
- priority_queue<int, vector<int>, greater<int>> right;
- public:
- /** initialize your data structure here. */
- MedianFinder() {
- left.push(INT_MIN);
- right.push(INT_MAX);
- }
- void addNum(int num) {
- int x = left.top();
- int y = right.top();
- if (num < x) {
- if (left.size() > right.size()) {
- left.pop();
- right.push(x);
- }
- left.push(num);
- } else if (num < y) {
- if (left.size() == right.size()) {
- left.push(num);
- } else {
- right.push(num);
- }
- } else {
- if (left.size() == right.size()) {
- right.pop();
- left.push(y);
- }
- right.push(num);
- }
- }
- double findMedian() {
- if (left.size() != right.size()) {
- return left.top();
- } else {
- return (double(left.top()) + right.top()) / 2;
- }
- }
- };
- /**
- * Your MedianFinder object will be instantiated and called as such:
- * MedianFinder* obj = new MedianFinder();
- * obj->addNum(num);
- * double param_2 = obj->findMedian();
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement