Sliding Window Median_2.cpp

class Solution {
public:
   vector<double> medianSlidingWindow(vector<int>& nums, int k) {
      int len = nums.size();
      multiset<int> smaller, larger;
      vector<double> res;
      for (int i = 0; i < len; ++i)
      {
          //erase
         if (i >= k)
         {
            if (smaller.find(nums[i - k]) != smaller.end())
               //pass iterator here otherwise it will erase all elements with the same value
               smaller.erase(smaller.find(nums[i - k]));
            else
               larger.erase(larger.find(nums[i - k]));
         }
          
         //insert
         if (smaller.size() <= larger.size())
         {
            if (larger.empty() || *larger.begin() >= nums[i])
               smaller.insert(nums[i]);
            else
            {
               smaller.insert(*larger.begin());
               larger.erase(larger.begin());
               larger.insert(nums[i]);
            }
         }
         else
         {
            if (*smaller.rbegin() <= nums[i])
               larger.insert(nums[i]);
            else
            {
               larger.insert(*smaller.rbegin());
               smaller.erase(--smaller.end());
               smaller.insert(nums[i]);
            }
         }
         if (i >= k - 1)
         {
            auto test1 = *smaller.rbegin(), test2 = *larger.begin();
            double mid = k % 2 ? (smaller.size() > larger.size() ? *smaller.rbegin() : *larger.begin()) :
               (static_cast<double>(*smaller.rbegin()) + static_cast<double>(*larger.begin())) / 2.0;
            res.push_back(mid);
         }
      }
      return res;
   }
};