有没有可能在少于O(n)的时间内从已排序的列表中删除重复项？

Question

我怀疑如果你可以比迭代子列表更快地定位重复值范围的另一端，那么就有可能实现保存。

- Nick Orton

---

“List”是什么意思？在链表中，遍历不可避免地是O（N）。如果你只是指“一些线性数据结构”，你可以在支持二进制或随机遍历的数据结构中使用二分查找（例如树或数组）。 - Jerry Coffin

如果排序算法具有O(nlogn)的时间复杂度，并且您可以在O(1)的时间内删除重复项，则总体复杂度仍为O(nlogn)。 - Nick Dandoulakis

澄清一下，我的意思是一种支持随机访问的线性数据结构，而不是树。我们称之为数组。 - Nick Orton

Answer 1

一般来说，不行。想象一下一个有N个重复项的列表，你需要进行N-1次删除，因此是O(N)。

如果你指定了一个具有优于O(1)元素删除的特定数据结构，那么对于某些特定类型的输入可能会有更好的方法。

即使你可以在O(1)时间内有效地删除一系列元素，并且找到重复项也需要O(1)时间 - 想象一下一个列表，其中有N/2对重复项。你仍然需要进行N/2次搜索和删除N/2个范围，两者都是O(N)。

（问题标题是“删除重复项”，但正文具体涉及删除一个范围，存在一些歧义）

如果你排序后得到的列表具有以下表示形式 - 每个节点都有一个值和该值的出现计数，那么删除一个值的重复项将简单地将该节点的计数设置为1。（skip list可能具有类似的特性，假设垃圾回收环境良好，在回收内存方面没有成本），因此对于一个重复项，它将是O(1)。如果你需要从列表中删除所有重复项，仍然是O(N)。

- Pete Kirkham

---

想象一下一个包含N个重复项的列表。你需要进行N-1次删除，因此时间复杂度为O(N)。但是，如果你知道重复项范围的起始和结束位置，那么你只需要进行一次删除。 - Jakub Konecki

@Jakub 嗯，其余部分可以在 O(1) 的时间内被切掉。正确释放将会得到 O(n) 的时间复杂度。 - ruslik

@ruslik - 请正确定义。在我看来，检查第一个和最后一个元素是否相等是正确的方法。 - Jakub Konecki

@Jakub 不，我指的是“remove”操作。如果您不关心释放内存，对于N个重复项，您可以进行一次单个删除。 - ruslik

@Jakub，我正在考虑使用特殊情况的数据结构，而不是单向链表。它不会是一个普通的列表，因为要找到块的另一端需要遍历；也许跳表可以在这种情况下解决问题。但它仍然无法帮助第二种情况。 - Pete Kirkham

@Pete Kirkham - 我明白了。如果这是一个链表，你无论如何都必须遍历所有元素才能到达末尾（以检查最后一个元素的值）。 - Jakub Konecki

Answer 2

一般而言是没有最好的时间复杂度，因为你总可以构造一个O(n)（没有重复元素的列表）的情况。然而，如果你对数据做出某些假设（例如最多有log n个不同的元素），你可能会得到更好的结果（对于这个特定的情况，我不确定）。

当然，这当然假设你有一种有效的“批量删除”的方法，意味着你可以以O(1)的时间删除任何相等元素的范围，而不管它的大小。

- Björn Pollex

Answer 3

不可能有

至于将所有元素与其他元素进行比较，我们需要进行n*(n-1)=n2-n次比较...`

- Genius

Answer 4

我会采用“二分查找”方法来查找范围的结束点：

假设我们有一个包含n个元素的排序列表。

1. 比较第一个和最后一个元素-如果相等，则整个列表是重复的。
2. 选择中间元素（n/2）
3. 对两个子列表递归执行搜索。

- Jakub Konecki

---

你是在说链表还是有序数组？ - Blagovest Buyukliev

如果列表中有N/2个重复项，那么我们如何不执行O(N)操作呢？ - Pete Kirkham

@Blagovest Buyukliev - 这有关系吗？ - Jakub Konecki

由于链表的元素没有随机访问的特性，无法真正实现二分查找。那么如何在O(1)时间复杂度内“选择中间元素”？ - Blagovest Buyukliev

@Jakub，这就是我想说的：有些算法对于某些输入会在小于O(n)的时间内执行。但是，对于问题的最坏情况，我无法想象出一个小于O(n)的算法。 - ruslik