关于Java:算法

关注
关于Java:算法www.shan-machinery.com

简短问题:

是否有任何数据结构或算法允许在恒定时间内按索引检索,插入和删除?

详细来说,我想解决以下问题(在Java中):

给定一个正数集合,创建一个数据结构,该数据结构允许进行以下操作以授予恒定的时间(最多可使用50-70MB):

随时获取最大或最小元素(仅一个就足够了)。

删除并插入给定索引。

我试图将元素放在一个已排序的数组中,并且每次删除顶部(最大或最小)元素时,都用一个负数标记它,然后增加指向顶部元素的索引,例如:123456789101112# sortedArr[headIndex] = topElementsortedArr = [30, 20, 9, 5, 3, 2, 1]headIndex = 0Delete top element (30)sortedArr = [-1, 20, 9, 5, 3, 2, 1]headIndex = 1Delete top element again (20)sortedArr = [-1, -1, 9, 5, 3, 2, 1]headIndex = 2

当删除的元素不是顶部元素时,问题就来了,因为我会失去对顶部元素的跟踪:

123456789101112# sortedArr[headIndex] = topElementsortedArr = [-1, -1, 9, 5, 3, 2, 1]headIndex = 2Delete number"3"sortedArr = [-1, -1, 9, 5, -1, 2, 1]headIndex = 2  # It is not updated as no top element has been removed.Delete number"5" and"9"sortedArr = [-1, -1, -1, -1, -1, 2, 1]headIndex = ?

HeadIndex应该为5,但是问题在于更新headIndex的方式是每次删除都无法将headIndex指向新的top元素,因此这就是为什么要求上述数据结构的原因。

类似于双栈结构的结构,它允许在任何适合我的地方进行删除和插入。

相关讨论我真的不明白您怎么能说这个问题太广泛了。我试图减少它,因为我是StackOverflow的新手,所以我仍然不知道如何正确发布。我的评论是针对@Bohemian的,我认为我没有理由关闭它@JeremyP哦,我知道了,还是谢谢你。这类事情的实际解决方案使用有序的,平衡的树。通过保留每个节点的子计数,子树中的max和子树统计中的min,您可以在O(log N)中进行所有操作。红黑树或B树是流行的实现。@MattTimmermans我将尝试这种方法,我只是担心由于O(log N),该解决方案对我而言并不完全有效,无论是否值得尝试。

想到的BitSet 2 ^ 31位将需要2 ^ 28字节,即256 MiB。不要求,但也可以有效地进行迭代。

123BitSet bitSet = ...;int max = bitSet.previousSetBit(bitSet.size() - 1);int min = bitSet.nextSetBit(0);

包括上一个和下一个方法。

如果没有删除,则将在O(1)中计算max,但是不幸的是min并非如此。由于这是稀疏数组的一种形式,因此两者的一般复杂度为O(n)。

相关讨论我确实发现尺寸令人惊讶地小。已更正您如何在恒定时间内找到一个位元组中的最大元素?@JoopEggen您好,感谢您的快速响应,您的意思是使用BitSet跟踪哪些号码已被删除?如果是这样,它在迭代时是否保持插入顺序?@DavidIvorra更简单,设置为:对于值13:bitset.set(13);(添加),bitset.clear(13)(删除),cardinality()(大小)@JeremyP size(),我希望还有previousSetBit(size() + 1)@JoopEggen似乎是一种非常有趣的方法,在我对其进行测试之后,我将告知该解决方案是否适合我。size()不会告诉您最大值(或最小值),而是告诉您BitSet中有多少个数字,即有多少位被设置为1。@JeremyP否cardinality()会这样做,size()给出words.length * BITS_PER_WORD;,因此其当前容量。不可否认,然后必须执行previousSetBit。与Set和其他集合不完全相同的术语。是的,您是对的,但我的问题仍然存在。如何在恒定时间内找到最大和最小元素(这是问题的要求)。在这方面,@ JeremyP BitSet无法提供O(1)。我应该发表评论,但是BitSet是一个被低估的类,例如用于设置范围3-42:s.set(3, 43)。考虑一下,如果您记录最小值和最大值,并根据需要对插入和删除进行调整,则除delete之外的所有操作都是恒定时间,如果删除最大值或最小值,则需要线性搜索,即使该值也是恒定的(n-2)/ n次可能删除的时间。@JoopEggen感谢您正确编辑响应,因此,是否有理由认为,如果在删除顶部元素时强制降低BitSet的容量(或大小),则max操作将始终保持不变?JeremyP您具体指的是始终跟踪最大值和最小值并调整插入和删除操作吗?@JeremyP也许我应该在这个问题中解释过,我实际上对数字集合所做的事情是对递归函数" f"的一系列调用。在删除数字的地方,获取最大数字,对修改后的集合调用" f",最后恢复集合,将数字重新插入到正确的位置。不幸的是,@ DavidIvorra size()表示实际的位容量,并且没有人会删除(通过数组副本)缩小数组,因为它甚至会变成O(n)。因此,始终需要对从先前的最大值到新的最大值的单词进行迭代。只需尝试BitSet-没有太多选择。@JoopEggen谢谢,尽管时间表现仍然是一个问题,但似乎这比我的想法更清洁。仍在思考是否可以轻松实现解决此问题的数据结构。

https://www.shan-machinery.com