0480. Sliding Window Median =========================== 题目信息 -------- :题号: 0480 :难度: Hard :主题: 连续窗口、中位数、奇偶长度、浮点结果 :原题: `LeetCode 0480 `_ :重点: 窗口长度固定为 ``k``、每次右移一位、偶数窗口取中间两数平均、按窗口顺序返回 题目重述 -------- 给定整数数组 ``nums`` 和整数 ``k``,长度为 ``k`` 的连续窗口从数组最左端开始,每次向右移动一个位置,直到覆盖最后 ``k`` 个元素。返回每个窗口的中位数组成的数组。 把窗口元素排序后,若 ``k`` 为奇数,中位数是正中间的元素;若 ``k`` 为偶数,中位数是中间两个元素的算术平均值。``nums.length`` 位于 ``[1, 10^5]``,元素在 32 位有符号整数范围内,``k`` 位于 ``[1, nums.length]``。答案允许 ``10^-5`` 以内的浮点误差。 自建示例 -------- 奇数长度窗口: .. code-block:: text 输入:nums = [2,1,4,7,2],k = 3 输出:[2.0,4.0,4.0] 解释:三个窗口排序后分别为 [1,2,4]、[1,4,7]、[2,4,7],中间值依次为 2、4、4。 偶数长度窗口: .. code-block:: text 输入:nums = [1,5,2,8],k = 2 输出:[3.0,3.5,5.0] 解释:每个窗口包含两个数,中位数分别是 (1+5)/2、(5+2)/2、(2+8)/2。 两个有序集合维护窗口中位位置 ------------------------------ 把当前窗口拆成 ``lower`` 和 ``upper`` 两个多重集合:``lower`` 保存较小的一半,且最多比 ``upper`` 多一个元素;``upper`` 保存较大的一半。每次加入或移除元素后,移动两个集合的边界元素恢复大小平衡,于是奇数窗口的中位数是 ``lower`` 最大值,偶数窗口的中位数是两边界的平均值。 使用 ``multiset`` 而不是 ``set``,因为窗口中可能有重复数字;删除时只删除一个与待移出值相等的迭代器。插入新元素和移除旧元素都发生在窗口右移的同一轮。 C++ 实现 -------- .. code-block:: cpp class Solution { std::multiset lower; std::multiset upper; void rebalance() { while (lower.size() > upper.size() + 1) { auto it = std::prev(lower.end()); upper.insert(*it); lower.erase(it); } while (lower.size() < upper.size()) { auto it = upper.begin(); lower.insert(*it); upper.erase(it); } } void add(long long value) { if (lower.empty() || value <= *lower.rbegin()) { lower.insert(value); } else { upper.insert(value); } rebalance(); } void eraseValue(long long value) { auto lowerIt = lower.find(value); if (lowerIt != lower.end()) { lower.erase(lowerIt); } else { upper.erase(upper.find(value)); } rebalance(); } double median(int k) { if (k % 2 == 1) return static_cast(*lower.rbegin()); return (*lower.rbegin() + *upper.begin()) / 2.0; } public: std::vector medianSlidingWindow(std::vector& nums, int k) { lower.clear(); upper.clear(); std::vector result; for (int i = 0; i < static_cast(nums.size()); ++i) { add(nums[i]); if (i >= k) eraseValue(nums[i - k]); if (i >= k - 1) result.push_back(median(k)); } return result; } }; 代码分析 -------- 平衡后 ``lower`` 的大小在奇数窗口时比 ``upper`` 多一、偶数窗口时相等,并且所有 ``lower`` 元素不大于所有 ``upper`` 元素,因此边界正好给出中位数。每个元素只插入和删除一次,时间复杂度为 ``O(n log k)``,额外空间复杂度为 ``O(k)``。