raghuvanshraj

295.cpp

Jul 30th, 2021
663
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class MedianFinder {
  2.     priority_queue<int> left;
  3.     priority_queue<int, vector<int>, greater<int>> right;
  4. public:
  5.     /** initialize your data structure here. */
  6.     MedianFinder() {
  7.         left.push(INT_MIN);
  8.         right.push(INT_MAX);
  9.     }
  10.    
  11.     void addNum(int num) {
  12.         int x = left.top();
  13.         int y = right.top();
  14.         if (num < x) {
  15.             if (left.size() > right.size()) {
  16.                 left.pop();
  17.                 right.push(x);
  18.             }
  19.             left.push(num);
  20.         } else if (num < y) {
  21.             if (left.size() == right.size()) {
  22.                 left.push(num);
  23.             } else {
  24.                 right.push(num);
  25.             }
  26.         } else {
  27.             if (left.size() == right.size()) {
  28.                 right.pop();
  29.                 left.push(y);
  30.             }
  31.             right.push(num);
  32.         }
  33.     }
  34.    
  35.     double findMedian() {
  36.         if (left.size() != right.size()) {
  37.             return left.top();
  38.         } else {
  39.             return (double(left.top()) + right.top()) / 2;
  40.         }
  41.     }
  42. };
  43.  
  44. /**
  45.  * Your MedianFinder object will be instantiated and called as such:
  46.  * MedianFinder* obj = new MedianFinder();
  47.  * obj->addNum(num);
  48.  * double param_2 = obj->findMedian();
  49.  */
RAW Paste Data