取某个窗口中的中位数

10 Nov 2024 in Algorithm Pageviews

滑动窗口

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间两个数的平均数。

示例：

给出 nums = [1,3,-1,-3,5,3,6,7]，以及k = 3。

[1 3 -1] -3 5 3 6 7 : 1

1 [3 -1 -3] 5 3 6 7 : -1

1 3 [-1 -3 5] 3 6 7 : -1

1 3 -1 [-3 5 3] 6 7 : 3

1 3 -1 -3 [5 3 6] 7 : 5

1 3 -1 -3 5 [3 6 7] : 6

因此返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]

代码实现如下：

class Solution {
public:
    vector<double> MedianSlidingWindow(vector<int> &nums, int k) {
        vector<double> res;
        multiset<double> ms(begin(nums), begin(nums) + k);
        auto left = begin(ms);
        advance(left, (k - 1) / 2);
        for (int i = k; i <= nums.size(); i++) {
            auto mid = ((k & 1) ? *left : (*left + *next(left)) / 2.0);
            res.emplace_back(mid);
            if (i == nums.size()) {
                break;
            }
            ms.insert(nums[i]);
            if (nums[i] < *left) {
                --left;
            }
            
            if (nums[i - k] <= *left) {
                ++left;
            }
            ms.erase(ms.lower_bound(nums[i - k]));
        }
        return res;
    }
};