c++ - 沿着一长串数据在固定大小的移动窗口中找到中值

Question

给定一个数据序列(它可能有重复项)，一个固定大小的移动窗口，在每次迭代时从数据开始移动窗口序列，使得(1) 从窗口中移除最旧的数据元素并生成一个新数据元素被插入窗口(2) 求每次移动时窗口内数据的中位数。

以下帖子没有帮助。

Effectively to find the median value of a random sequence

joining data based on a moving time window in R

我的想法:

使用 2 个堆来存放中位数。在窗口旁边，对窗口中的数据进行排序在第一次迭代中，最小堆持有较大的部分和最大堆持有较小的部分。如果窗口有奇数个数据，最大堆返回中位数，否则返回顶部元素的算术平均值两堆是中位数。

当一个新的数据被插入窗口时，从一个窗口中移除最旧的数据堆并将新数据与最大和最小堆的顶部进行比较决定将数据放在哪个堆上。然后，找到中位数就像在第一次迭代中一样。

但是，如何在堆中找到数据元素是个问题。堆是二进制的树不是二叉搜索树。

是否可以用 O(n) 或 O(n * lg m) 来解决它，其中 m 是窗口大小，空间:O(1)？

非常感谢任何帮助。

谢谢

Answer 1

O(n*lg m) 很简单:

只需将您的窗口维护为两个 std::set，一个用于下半部分，一个用于上半部分。插入新元素的成本为 O(lg m)，查找和删除旧元素的成本相同。使用您在问题中描述的方法确定中位数的成本为 O(1)。

当您在序列上滑动窗口时，在每次迭代中，您删除掉落在窗口外的项目 (O(lg m))，插入新项目 (O(lg m)) 并计算中值 (O( 1)), 导致总共 O(n lg m)。

当然，此解决方案使用空间 O(m)，但我认为您无法在不存储窗口内容的情况下逃脱。