代码之家 › 专栏 › 技术社区 › Valerio Schiavoni

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

duplicate-removal lua

1

Valerio Schiavoni · 技术社区 · 16 年前

我有一个数组,它可能包含重复的对象。我想知道是否可以找到和删除数组中的重复项: -无排序(严格要求) -不使用临时辅助数组 -可能在o(n)中,n是数组中元素的nb

在我的例子中,数组是一个Lua数组,其中包含表:

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

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

4 回复 | 直到 14 年前

1

3

sbk 16 年前

总而言之,您有以下选项:

挑一个。在没有额外记忆的情况下,没有办法做你想做的事。

2

arclight 16 年前

不能在O(N)中完成,但是…

你能做的就是

最坏情况下的方案复杂性为o(n^2)

3

0

Byron Whitlock 16 年前

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

4

0

AbstractDissonance 14 年前

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

可以覆盖对象插入以防止插入重复项。这是每个对象插入的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)。内存足迹是产品(n_k,k=1..m)的节点数(通常可以减少一个数量级或可能减少n_m)。