use*_*288 11 c++ algorithm median data-structures
给定一系列数据(可能有重复数据),固定大小的移动窗口,从数据序列的开始每次迭代移动窗口,以便(1)从窗口中移除最旧的数据元素并且新的数据元素被推入窗口(2)在每次移动时找到窗口内数据的中值.
以下帖子没有帮助.
我的想法:
使用2堆来保持中位数.在窗口旁边,在第一次迭代中对窗口中的数据进行排序,最小堆保存较大的部分,最大堆保存较小的部分.如果窗口具有奇数个数据,则最大堆返回中值,否则两个堆的顶部元素的算术平均值是中值.
将新数据推入窗口时,从其中一个堆中删除最旧的数据,并将新数据与max和min堆的顶部进行比较,以便确定要将数据放入哪个堆.然后,找到中间值就像在第一次迭代中一样.
但是,如何在堆中查找数据元素是一个问题.堆是二叉树而不是二叉搜索树.
是否有可能用O(n)或O(n*lg m)求解它,其中m是窗口大小和空间:O(1)？
任何帮助都非常感谢.
谢谢
hc_*_*hc_ 10
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),但我不认为你可以在不存储窗口内容的情况下逃脱.
我几乎完全实现了你在这里描述的算法:http://ideone.com/8VVEa,并在此处描述: C中的滚动中位数 - Turlach实现
解决"找到最旧"问题的方法是将值保存在循环缓冲区中,因此始终指向最旧的缓冲区.存储在堆中的是缓冲区索引.因此空间要求为2M,每次更新为O(lg M).