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

迭代数组，将每个值添加到哈希表中，并先检查是否存在。如果存在，则从原始数组中移除（或不写入新数组）。这种方法的内存使用效率不高，但时间复杂度仅为 O(n)，因为仅迭代一次数组。

无法在O(n)内完成，但是...

你可以做以下事情：

• 遍历整个数组
• 对于每个元素，向前搜索重复项，并将其删除。

最坏情况下的复杂度为O(n^2)。

总之，您有以下选项：

• 时间：O(n^2)，无额外内存 - 为数组中的每个元素线性查找相等的元素
• 时间：O(n*logn)，无额外内存 - 先排序，在线性遍历数组
• 时间：O(n)，内存：O(n) - 使用查找表（编辑：我记得表不能是其他表的键）

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

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

你可以覆盖对象插入以防止插入重复项。这是每个对象插入的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亿访问时间相比，它的速度快了10000万倍，内存比二叉树少了1000倍，但速度却慢了100倍！（当然，维护树的一些开销可能会减少）。

如果我们使用二叉树，则深度约为40。问题在于有约1万亿个节点，因此需要大量的额外内存。通过在每个节点中存储多个值（并且在上述情况下每个节点实际上部分值和其他树），我们可以显着减少内存占用，但仍可获得令人印象深刻的性能。

基本上，线性访问在较低的数字时占优势，而树在高数字时占优势。树消耗更多的内存。通过使用多棵树，我们可以结合两种世界的优点，即在线性访问小数字并具有较多元素的节点（与二叉树相比）。

这样的树不是很容易创建，但基本上遵循标准二叉树、红黑树、AVL树等的算法性质...

因此，如果您处理大型数据集，则对性能和内存不是一个巨大问题。基本上，正如你可能知道的那样，随着一个的增加，另一个会下降。多树会找到最佳媒介。 （假设您正确选择了节点大小）

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