algorithm - 允许通过索引访问元素并在 O(1) 中删除它们的数据结构

Question

我有以下任务(作为更大任务的一部分):

我需要从类似数据结构的数组中取出一个 k 元素并将其删除(k 是任何可能的索引)。 Array 的删除元素复杂度为 O(n)，List 的查找元素复杂度为 O(n)。我想在 O(1) 时间内完成这两个操作。

我应该使用哪种数据结构来满足这个要求？

澄清:

删除 index(5) 上的元素会将元素从 index(6) 移动到 index(5)。

此特定任务是 topcoder srm 300 div2 500 点问题。它不需要如此复杂的数据结构(简单的 java 方法就可以完成这项工作，因为最大数据非常小)，但我很好奇如何使用类似 c 的数据思考来处理更大的问题。

所以也许我对这个问题坚持了很多？但我会在下类后分析它并编辑问题(如果你真的很好奇，你可以在 top coder 上看到任务)。

Answer 1

我相信你要求的是不可能的。

但是，如果您可以放宽索引到 O(log n) 的要求，那么 ropes也许能够满足它，虽然我不确定他们是否有概率或确定性保证(我认为它是概率性的)。