Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- vector<double> medianSlidingWindow(vector<int>& nums, int k) {
- multiset<int>mst(nums.begin(),nums.begin()+k);
- vector<double>ans;
- auto p = next(mst.begin(),k/2); // poiter to the median
- int n = nums.size();
- for(int i=k;;i++)
- {
- double md = (((double)*p + *prev(p,1-(k%2))) / 2);
- ans.push_back(md);
- if(i==nums.size())return ans;
- mst.insert(nums[i]);
- if(nums[i] < *p)p--; /// Here relative order matter if we switch nums[i]>*p ,p++ it will give WA.
- if(nums[i-k] <= *p)p++;
- mst.erase(mst.lower_bound(nums[i-k]));
- }
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement