如何删除数组的第i个元素，且使得操作时间不依赖于数组的长度n？如果不能打乱顺序又该怎样操作呢？

Question

我是这样想的：既然是数组，那么根据下标就可以访问任意元素，而且大小固定。那么，如果想操作时间不依赖于长度n的话，可以直接将第n-1个元素，即最后一个元素复制到第i个的位置上，然后最后一个元素赋某个特殊值。

对于第二个问题，我觉得可以将第i个之后的元素依次向前平移，然后最后一个元素赋特殊值。

我在某个群里看到了其他答案，他是用其他数据结构重新实现数组，比如链表、二叉树。但是，我认为数组就是数组，具有连续的存储空间，用其他方式实现的就不是数组，而且数组是比较基本的数据结构。

我想知道大家的看法和答案是什么？

Answer 1

我觉得用链表可以比较好的符合不依赖长度的要求，毕竟数组删除要大量移动…暂时没有想到更好的，坐等更好解决方案。

Answer 2

我是这样想的：既然是数组，那么根据下标就可以访问任意元素，而且大小固定。那么，如果想操作时间不依赖于长度n的话，可以直接将第n-1个元素，即最后一个元素复制到第i个的位置上，然后最后一个元素赋某个特殊值。

对于第二个问题，我觉得可以将第i个之后的元素依次向前平移，然后最后一个元素赋特殊值。

（然后这个特殊值代表本元素指向被删除的i元素）

然后你就光荣的重新创造了数组+链表了。2333333333

Answer 3

用哈希表实现的数组（字典）{1:a[1], 2:a[2], 3:a[3] ...}应该可以满足要求。删除操作接近于常数时间。

Answer 4

按题主的意思，此处数组是连续存储的。想要o(1)删除任意位置元素且保持删除后数组的连续性是没办法做到的。如果不保持连续性，可考虑将删除位置赋特殊值，对下标访问和迭代器遍历作相应处理，上述操作保持接近o(1)的复杂度不难。一个维持连续性的权衡之计：在进行n/log(n)次删除操作后，重建连续性，这样删除操作的复杂度是o(log(n))。

Answer 5

如果可以将n-1的元素直接复制到i的位置上，那么下标还有什么意义？