algorithm - 具有 O(1) 删除任何元素的动态数组

Question

这道题是我想到的一个数据结构。它是一个动态数组，类似于C++中的std::vector<>，只是移除算法不同。

在一个普通的动态数组中，当一个元素被移除时，所有剩余的元素必须向下移动，这是 O(n)，除非它是最后一个元素，这将是 O(1)。

在这个中，如果删除了任何元素，它将被最后一个元素替换。这当然会丢失元素的顺序。但是现在删除任何元素都是常数时间。

列表将具有相同的删除时间，但此结构具有随机访问。唯一需要注意的是你不知道你在访问什么，因为排序可能会困惑，所以无论如何使用随机访问。另外，列表不会弄乱任何指向元素的指针/迭代器。

嗯，除了严格遍历元素并可能沿途删除它们的非常具体的任务外，这种结构似乎毫无用处。列表可以做同样的事情，但它有更好的缓存性能。

那么，这个奇怪/无用的结构有名字吗，它有什么用处吗？或者只是一个不错的小头脑 Storm ？

Answer 1

这个想法用在Knuth (Fisher–Yates) shuffle .随机选取的元素将替换为数组中的最后一个元素。由于无论如何我们想要的是随机排列，因此重新排序并不重要。