lua - 如何在不排序的情况下从数组中删除重复项

Question

我有一个可能包含重复对象的数组。我想知道是否可以找到并删除数组中的重复项： - 不排序（严格要求） - 不使用临时辅助数组 - 可能在 O(N) 中，N 是数组中元素的 nb

在我的例子中，该数组是一个 Lua 数组，其中包含表：

t={
{a,1},
 {a,2},
 {b,1},
 {b,3},
 {a,2}
}

在我的例子中，t[5] 是 t[2] 的副本，而 t[1] 不是。

score 3 · Accepted Answer

总而言之，您有以下选择：

选一个。在没有额外内存的情况下，没有办法在 O(n) 时间内做你想做的事。

score 2 · Accepted Answer

不能在 O(n) 中完成，但是......

你能做的是

最坏情况的复杂度是 O(n^2)

score 0 · Accepted Answer

迭代数组，将每个值粘贴在哈希中，首先检查它是否存在。如果它确实从原始数组中删除（或不写入新数组）。内存效率不是很高，但只有 0(n)，因为您只迭代数组一次。

score 0 · Accepted Answer

是的，取决于你如何看待它。

您可以覆盖对象插入以防止插入重复项。这是每个对象插入的 O(n)，对于较小的数组可能感觉更快。

如果您提供排序的对象插入和删除，那么它是 O(log n)。本质上，您始终在插入和删除时保持列表排序，以便查找元素是二进制搜索。这里的代价是元素检索现在是 O(log n) 而不是 O(1)。

这也可以使用诸如红黑树和多树之类的东西有效地实现，但要以额外的内存为代价。这样的实现为某些问题提供了几个好处。例如，通过使用嵌套树，我们可以拥有 O(log n) 类型的行为，即使是非常非常大且内存占用很小的表。顶层树提供了数据集的一种配对向下概述，而子树在需要时提供更精细的访问。

例如，要看到这个假设我们有 N 个元素。我们可以将其划分为 n1 个组。然后可以将这些组中的每一个进一步划分为 n2 个以上的组，并将这些组划分为 n2 个组。因此我们的深度为 N/n1n2...

如您所见，即使对于较小的 n，n 的乘积也会很快变得非常大。如果 N = 1 万亿个元素并且 n1 = 1000、n2 = 1000、n3 = 1000，则每次访问时间只需 1000 + 1000 + 1000 + 1000 s = 4000。此外，我们每个节点的内存占用只有 10^9 次。

将此与直接线性搜索所需的平均 5000 亿访问时间进行比较。它比二叉树快 1 亿多倍，内存少 1000 倍，但慢约 100 倍！（当然，保持树的一致性有一些开销，但即使这样也可以减少）。

如果我们使用二叉树，那么它的深度大约为 40。问题是大约有 1 万亿个节点，所以这是一个巨大的额外内存。通过为每个节点存储多个值（在上述情况下，每个节点实际上是部分值和其他树的值），我们可以显着减少内存占用，但仍然具有令人印象深刻的性能。

基本上线性访问在数量较少时占优势，而树在数量较多时占优势。树的。树的消耗更多的内存。通过使用多树，我们可以通过对较小数字使用线性访问和每个节点具有更多元素（与二叉树相比）来结合两全其美。

这种树的创建并非易事，但基本上遵循标准二叉树、红黑树、AVL 树等的相同算法性质......

因此，如果您正在处理大型数据集，这对于性能和内存来说并不是一个大问题。从本质上讲，您可能知道，随着一个上升，另一个下降。多树的，有点找到最佳媒介。（假设您正确选择了节点大小）

多树的深度是 N/product(n_k,k=1..m)。内存占用是 product(n_k,k=1..m) 的节点数（通常可以减少一个数量级或可能 n_m）

4 回答 4