昨天我参加了算法分析考试，题目是描述如何在阵列上实现以下每个操作，以便所需时间不取决于阵列大小n。
-
删除大小为n的数组的第i个元素。
-
删除已排序数组的第i个元素，该数组保留在删除后的排序顺序。
对于第一部分，我们可以将第I个值与最后一个值交换，这就是我所写的，而对排序后的数组这样做将不起作用，因为数组将不排序。现在的问题是，如何为排序数组实现这一点？有可能做到这一点而没有任何缺点吗？对于未排序的数组，我们能用更好的方法吗？
我认为这个问题的目的是让您了解数组和列表之间的区别。在前者中，您可以任意访问，但删除和添加将需要移动索引。但是，在列表中，一旦到达节点，就可以在恒定时间内添加/删除节点。但是，由于您没有任意访问权限，因此到达需要O（n）。如果这是你的提问者的想法，我想他/她希望你创建一个像List一样的数据结构，但要有索引——比如Java的ArrayList。
但是，您也可以使用数组来解决这个问题，只需保留一个已删除的索引列表。如果要删除array[i]，只需保留一个新列表"deletedIndices"并添加"i"即可。因此，删除将花费恒定的时间和空间。不需要添加哨兵。
编辑：为了回答你关于我的评论的问题，不，跳过不会花费O（n）。这是一个简单的列表更新。此外，尽管问题不是什么，但值得知道的是，阵列的所有未来遍历都需要遍历新列表，以便知道何时跳过。如果列表始终保持排序，则可以有效地做到这一点。我们可以通过简单地遍历列表一次来确定放置新传入对象的位置。这需要O（n）。因此，综上所述，删除发生在恒定的时间内，但遍历仍然需要O（n）+O（n
a用最后一个元素替换第i个元素并减少数组尺寸乘以1。
b用不能为值的特殊符号替换第i个元素要标记的数组元素的值（例如，0表示正数数组）第i个位置为空。（这种方法有时被称为"懒惰"删除"。）
用一个特殊符号替换第i个元素，该符号不能是数组元素的值（例如，0表示正数数组），以将第ith位置标记为空。（这种方法有时被称为"延迟删除"。）