leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0295.cpp (731B)

      1 class MedianFinder {
      2     priority_queue<int> left;
      3     priority_queue<int, vector<int>, greater<int>> right;
      4 
      5   public:
      6     void addNum(int num) {
      7         if (left.empty() || num < left.top())
      8             left.push(num);
      9         else
     10             right.push(num);
     11 
     12         if (left.size() < right.size()) {
     13             int temp = right.top();
     14             right.pop();
     15             left.push(temp);
     16         }
     17 
     18         if (left.size() - right.size() > 1) {
     19             int temp = left.top();
     20             left.pop();
     21             right.push(temp);
     22         }
     23     }
     24 
     25     double findMedian() {
     26         if (left.size() > right.size())
     27             return left.top();
     28         else
     29             return (left.top() + right.top()) * 0.5;
     30     }
     31 };