-
Notifications
You must be signed in to change notification settings - Fork 0
/
Sliding Window Median.cpp
51 lines (49 loc) · 1.75 KB
/
Sliding Window Median.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
/**
* @param nums: A list of integers.
* @return: The median of the element inside the window at each moving
*/
vector<int> medianSlidingWindow(vector<int> &nums, int k) {
// write your code here
map<int, int> maxnum, minnum;
int n = nums.size(), maxcount = 0, mincount = 0;
vector<int> ans;
if(k > n) k = n;
for(int i = 0; i < n; i++) {
if(i >= k) {
if(maxnum.find(nums[i-k]) != maxnum.end()) {
maxnum[nums[i-k]]--;
if(maxnum[nums[i-k]] == 0) maxnum.erase(nums[i-k]);
maxcount--;
} else {
minnum[nums[i-k]]--;
if(minnum[nums[i-k]] == 0) minnum.erase(nums[i-k]);
mincount--;
}
}
if(minnum.empty() ||(!maxnum.empty() && prev(maxnum.end())->first >= nums[i])) {
maxnum[nums[i]]++;
maxcount++;
} else {
minnum[nums[i]]++;
mincount++;
}
if(maxcount > mincount+1) {
auto iter = prev(maxnum.end());
minnum[iter->first]++;
iter->second--;
if(iter->second == 0) maxnum.erase(iter);
maxcount--; mincount++;
} else if (mincount > maxcount) {
auto iter = minnum.begin();
maxnum[iter->first]++;
iter->second--;
if(iter->second == 0) minnum.erase(iter);
maxcount++; mincount--;
}
if(i >= k-1) ans.push_back(prev(maxnum.end())->first);
}
return ans;
}
};