gpt4 book ai didi

data-structures - 如何维护有序的滑动窗口

转载 作者:行者123 更新时间:2023-12-02 03:12:17 25 4
gpt4 key购买 nike

这个问题与编程语言无关。那么问题来了:

我有一个大小为 n 的滑动窗口,其中包含实数。如果该滑动窗口已满,则每次新插入时都会删除旧值(先进先出方式)。时不时地(K次),我需要特定索引中的值,每个查询的索引都不同,该窗口内的有序值。所以我必须花费 O(K*nlog(n)) 对窗口进行排序,并花费 O(1) 来获取我的值。有可能降低这种复杂性吗?在最坏的情况下(经常发生),我必须对每个新条目的窗口进行排序。

我正在考虑维护滑动窗口值的索引并维护排序列表。这会节省排序的复杂性,但是插入或删除的复杂性是多少呢?另外,这样的数据结构是否已经存在?

最佳答案

如果您在订单统计树 ( https://en.wikipedia.org/wiki/Order_statistic_tree ) 中维护窗口(大小为 n)个元素,那么您将花费 O(log n) 时间来推进窗口,并且 >O(log n) 时间查找窗口中任意 i 的第 i 个最大元素。如果您必须经常进行查询,这将非常有利。

顺序统计树只是一个平衡的二叉搜索树,其中每个节点都根据其子树的大小进行扩展,这使您可以直接向下钻取给定排名的元素。

关于data-structures - 如何维护有序的滑动窗口,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57258759/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com