Sliding Window Median_1.cpp

class Solution {
public:
   vector<double> medianSlidingWindow(vector<int>& nums, int k) {
      int len = nums.size();
      multiset<int> set(nums.begin(), nums.begin() + k);
      auto mid = next(set.begin(), k / 2);
      vector<double> res;
      for (int i = k; i <= len; ++i)
      {
         res.push_back((static_cast<double>(*mid) + static_cast<double>(*prev(mid, 1 - k % 2))) / 2.0);
         if (i == len)break;
         set.insert(nums[i]);
         if (nums[i] < *mid)--mid;
         if (nums[i - k] <= *mid)++mid;
         set.erase(set.lower_bound(nums[i - k]));
      }
      return res;
   }
};