C++如何计算数组的移动中位数-C++-PHP中文网

移动中位数指滑动窗口内元素的中位数，不能直接用std::nth_element因其时间复杂度高（o(n×k)）且会破坏原数组顺序；应使用两个multiset维护左右堆并动态平衡。

c++如何计算数组的移动中位数

什么是移动中位数，为什么不能直接用 `std::nth_element`

移动中位数（sliding median）指对一个固定长度窗口在数组上滑动，每次取窗口内元素的中位数。比如数组 {1,3,2,4,5}、窗口大小 3，结果是 {2,3,4}（对应子数组 {1,3,2}、{3,2,4}、{2,4,5} 的中位数）。

直接对每个窗口调用 std::nth_element 时间复杂度是 O(n × k)（n 是数组长度，k 是窗口大小），窗口大时很慢；而且 std::nth_element 会修改原数据顺序，若需保留原始数组或支持重复插入/删除，就不适用。

用两个 `std::multiset` 维护动态中位数

核心思路是把窗口内元素分成两半：较小的一半放进 left（最大堆语义，用 std::multiset 配合 std::greater<int></int>），较大的一半放进 right（最小堆语义）。始终保证：left.size() == right.size() 或 left.size() == right.size() + 1，这样中位数就是 *left.begin()（奇数窗口）或 (*left.begin() + *right.begin()) / 2.0（偶数窗口）。

滑动时需同步增删元素并重新平衡集合：

插入新元素：先插进 left，再把 left 最大值移到 right，再把 right 最小值移回 left，确保大小关系和尺寸约束
删除旧元素：先判断它在哪个 set 里（可用 find + 迭代器比较），再 erase(iterator)；注意 multiset::erase(value) 会删掉所有相等元素，必须用迭代器版本
平衡操作后，检查 left.size() 和 right.size() 是否满足条件，否则手动挪一个

示例关键片段：

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

std::multiset<int std::greater>> left;
std::multiset<int> right;

auto rebalance = [&]() {
    if (left.size() > right.size() + 1) {
        right.insert(*left.begin());
        left.erase(left.begin());
    } else if (right.size() > left.size()) {
        left.insert(*right.begin());
        right.erase(right.begin());
    }
};
</int></int>

注意 `std::multiset::erase` 的陷阱

滑动窗口中删除“过期”元素时，最容易出错的是误用 erase(key)。比如窗口含两个 3，当前要删最左边那个，若写 left.erase(3)，会把全部 3 删光。

正确做法是先找到对应迭代器：

用 left.find(val) 找到第一个匹配项（multiset::find 返回任意一个匹配迭代器）
但要注意：如果该值不在 left 中，find 返回 end()，必须判空再 erase
更稳妥的做法是分别维护左右 set 的元素计数（如用 std::unordered_map<int int></int> 记录待删数量），延迟清理（lazy deletion），避免频繁 find + erase 影响性能

延迟删除伪代码逻辑：

std::unordered_map<int int> to_remove;
// 删除时：to_remove[val]++;
// 插入/平衡前：while (!left.empty() && to_remove[*left.begin()] > 0) { to_remove[*left.begin()]--; left.erase(left.begin()); }
</int>