Advertisement
Guest User

Untitled

a guest
Sep 23rd, 2019
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.78 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     vector<double> medianSlidingWindow(vector<int>& nums, int k) {
  4.        
  5.         multiset<int>mst(nums.begin(),nums.begin()+k);
  6.         vector<double>ans;
  7.         auto p = next(mst.begin(),k/2); // poiter to the median
  8.         int n = nums.size();
  9.         for(int i=k;;i++)
  10.         {
  11.             double md = (((double)*p + *prev(p,1-(k%2))) / 2);
  12.             ans.push_back(md);
  13.             if(i==nums.size())return ans;
  14.            
  15.             mst.insert(nums[i]);
  16.             if(nums[i] < *p)p--;  /// Here relative order matter if we switch nums[i]>*p ,p++ it will give WA.
  17.            
  18.             if(nums[i-k] <= *p)p++;
  19.                
  20.             mst.erase(mst.lower_bound(nums[i-k]));
  21.            
  22.            
  23.         }
  24.        
  25.     }
  26. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement