arrays - 从数组中删除第 i 个元素，因此时间复杂度不依赖于数组大小

Question

昨天我参加了算法分析考试，题目是 描述如何在一个数组上实现以下每个操作，以便它所花费的时间不取决于数组大小 n。

• 删除大小为 n 的数组的第 i 个元素。

• 删除排序数组的第i个元素，其中数组保留在删除后排序。

对于第一部分，我们可以将第 i 个值与最后一个值交换，这就是我写的，而对排序数组执行此操作将不起作用，因为数组将变得未排序。现在的问题是，如何为排序数组实现这一点？有没有可能做到这一点而没有任何缺点？对于未排序的数组，我们能否以更好的方式做到这一点？

Answer 1

我认为这个问题的目的是让您了解数组和列表之间的区别。在前者中，您可以任意访问，但删除和添加将需要移动索引。但是，在列表中，您可以在到达节点后在恒定时间内添加/删除节点。但是，到达需要 O(n)，因为您没有任意访问权限。如果那是你的提问者的想法，我认为他/她希望你创建一个像 List 一样的数据结构，但有索引——就像 Java 的 ArrayList。

但是，您也可以通过简单地保留已删除的索引列表来使用数组解决此问题。如果要删除 array[i]，只需保留一个新列表“deletedIndices”并向其添加“i”。因此，删除将花费恒定的时间和空间。不需要添加哨兵。

编辑:为了回答您关于我的评论的问题，不，跳过不会花费 O(n)。这是一个简单的列表更新。此外，即使这不是问题所在，也值得知道数组的所有 future 遍历都需要遍历新列表以及知道何时跳过。如果列表始终保持排序，则可以有效地完成此操作。我们可以通过简单地遍历一次列表来确定将新传入对象放置在哪个位置。这将花费 O(n)。所以，总结一下，删除发生在常量时间，但是遍历还是会O(n) + O(n) = O(n) - 原数组遍历第一个大哦，链表遍历第二个大哦