Mind palace

some thoughts

0%

480. Sliding Window Median

Posted on Edited on In Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

multiset/hashheap O(nlogk)
跟239. Sliding Window Maximum方法不一样，太smart了
讨论一下添加删除的四种情况即可，两个if都能cover

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        multiset<int> s(begin(nums), begin(nums) + k);
        auto m = next(begin(s), k / 2);
        vector<double> res;
        for (int i = k; i <= n; ++i) {
            res.push_back((k & 1) ? *m : (*prev(m) + double(*m)) * 0.5);
            if (i == n) break;
            s.insert(nums[i]);
            if (nums[i] < *m) { // 偶变奇则需要前移
                --m;
            }
            if (nums[i - k] <= *m) { // 如果要删除的数有可能是*m要提前对m作调整，否则删除以后m就spoil了
                ++m; // 奇变偶需要后移
            }
            s.erase(s.find(nums[i - k]));
        }
        return res;
    }
};
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
class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        if (nums.empty()) return {};
        int n = nums.size();
        multiset<int> max, min;
        for (int i = 0; i < k; ++i) {
            max.insert(nums[i]);
        }
        for (int i = 0; i < k / 2; ++i) {
            min.insert(*max.rbegin());
            max.erase(max.find(*max.rbegin())); // Remember this usage!
        }
        vector<double> res;
        for (int i = k; i < n; ++i) {
            if (max.size() == min.size()) {
                res.push_back(*max.rbegin() / 2.0 + *min.begin() / 2.0); // (a + b) / 2.0 could overflow!
            }
            else {
                res.push_back(*max.rbegin());
            }
            if (max.count(nums[i - k])) {
                max.erase(max.find(nums[i - k]));
                max.insert(nums[i]);
            }
            else {
                min.erase(min.find(nums[i - k]));
                min.insert(nums[i]);
            }
            if (!max.empty() && !min.empty() && *max.rbegin() > *min.begin()) {
                int tmp = *max.rbegin();
                max.erase(max.find(tmp));
                max.insert(*min.begin());
                min.erase(min.begin());
                min.insert(tmp);
            }
        }
        if (max.size() == min.size()) {
            res.push_back(*max.rbegin() / 2.0 + *min.begin() / 2.0);
        }
        else {
            res.push_back(*max.rbegin());
        }
        return res;
    }
};