我有以下任务(作为更大任务的一部分):
我需要从类似数据结构的数组中取出一个 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 上看到任务)。
最佳答案
我相信你要求的是不可能的。
但是,如果您可以放宽索引到 O(log n) 的要求,那么 ropes也许能够满足它,虽然我不确定他们是否有概率或确定性保证(我认为它是概率性的)。
关于algorithm - 允许通过索引访问元素并在 O(1) 中删除它们的数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18052959/