5 arrays algorithm time-complexity
昨天我参加了算法分析考试，其中的问题是 描述如何在数组上实现以下每一项操作，以便所需时间不依赖于数组大小 n。
删除大小为 n 的数组的第 i 个元素。
删除已排序数组的第 i 个元素，删除后数组仍保持排序顺序。
对于第一部分，我们可以将第 i 个值与最后一个值交换，这就是我所写的，而对已排序的数组执行此操作将不起作用，因为数组将变得未排序。现在的问题是，如何对排序数组实现这一点？是否可以毫无缺点地做到这一点？对于未排序的数组，我们能以更好的方式做到这一点吗？
小智 3
我认为这个问题的目的是让您了解数组和列表之间的区别。在前者中，您可以任意访问，但删除和添加将需要移动索引。然而，在列表中，一旦到达节点，您就可以在恒定时间内添加/删除节点。但是，由于您没有任意访问权限，因此到达需要 O(n)。如果这是你的提问者的想法，我认为他/她希望你创建一个像 List 一样的数据结构，但带有索引 - 就像 Java 的 ArrayList 一样。
但是，您也可以通过简单地保留已删除索引的列表来使用数组来解决此问题。如果要删除 array[i]，只需保留一个新列表“deletedIndices”并向其添加“i”即可。因此，删除将花费恒定的时间和空间。不需要添加哨兵。
编辑：回答你对我的评论的问题，不，跳过不会花费 O(n)。这是一个简单的列表更新。另外，即使这不是问题所在，但值得知道的是，以后对数组的所有遍历也都需要遍历新列表才能知道何时跳过。如果列表始终保持排序，则可以有效地完成此操作。我们只需遍历一次列表就可以确定将新传入的对象放置在哪个位置。这将需要 O(n)。所以，总而言之，删除发生在常数时间内，但遍历仍然需要 O(n) + O(n) = O(n) - 第一个大哦用于原始数组遍历，第二个用于列表遍历