Easily understandable with only one <set> data structure.


  • 0
    T
    //Tian Xia (SummerRainET2008@gmail.com)    
    
    class MedianFinder {
     public:
      typedef pair<int, int> Pair;    // <Value, Position>    
      
      void addNum(int num) {
        buff_.insert(Pair(num, idx++));
        if (size_left == -1) {
          ite_mid_ = buff_.begin();
          size_left = 0;
        }
        if (num < ite_mid_->first) {
          size_left += 1;
        }
      }    
      
      double findMedian() {
        int size = buff_.size();
        return (size % 2 == 1 ?  
                get_kth_element(size / 2):
                (get_kth_element(size / 2 - 1) + get_kth_element(size / 2)) / 2);
      }
    
     protected:
      double get_kth_element(int k) {
        while (size_left < k) {
          size_left += 1;
          ++ite_mid_;
        }
        while (size_left > k) {
          size_left -= 1;
          --ite_mid_;
        }
        return ite_mid_->first;
      }
    
      set<Pair>   buff_;
      set<Pair>::iterator   ite_mid_;
      int        size_left = -1, idx = 0;
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.