假设有一个未排序的数组A，它包含的元素x（x是元素的指针），和每一个元素都有一个卫星变量k。因此，我们可以得到下面的时间复杂度（最坏情况下）：

Suppose there is a unsorted array A, and it contains an element x (x is the pointer of the element), and every element has a satellite variable k. So, we can get the following time complexity (for worst cases):

如果我们想搜索作为一个特定的K，那么它的成本为O（n）。

If we want to Search for a particular K, then it costs O(n).

如果我们想插入的元素，那么它的成本O（1），因为A只是增加元素进行到底。

if we want to Insert an element, then it costs O(1), because A just adds the element to the end.

如果我们知道x，则删除是数组中的一个？

What if we know x, then Delete it from the array A?

我们需要的搜索的为XK第一和x的索引，那么的删除 X通过它的A股指数，对不对？

We have to Search for x.k first and get the index of x, then Delete x via its index in A, right?

因此​​，对于删除，它的成本为O（n）也一样，对吧？

So for Delete, it costs O(n) too, right?

感谢

推荐答案

查找元件与给定的值是线性的。

Finding the element with a given value is linear.

由于数组无论如何都不会进行排序，你可以删除自身在不断的时间。第一个交换要删除的数组的末尾元素，然后通过一个元素减少数组的大小。

Since the array isn't sorted anyway, you can do the deletion itself in constant time. First swap the element you want to delete to the end of the array, then reduce the array size by one element.