如何在$ Mathcal {o}（n log n）$ time中清除链接列表？

Question

我想知道如何从$ mathcal {o}（n lg n）$ time中的链接列表中删除重复值。我有一个想法，即当我们想比较选择小的元素时，如果它们在指针上是平等的前进，并且只需考虑一个元素，则使用合并排序。还有其他选择吗？

Answer 1

1. 对$ O（n log n）$时间的链接列表进行排序。
2. 如果与$ O（n）$时间中的前一个相同，则浏览列表中的每个元素并删除元素。

总复杂性为$ O（n log n）$，这是您要搜索的。

Answer 2

您可以在$ o（n）$中执行此操作。

1）通过穿越链接列表并将其元素添加到哈希表中来构建哈希表。在每次迭代中，搜索哈希表查看迭代中要考虑的当前元素。如果找不到元素，请添加到哈希表中元素值作为键，而为1作为相应值。如果您找到元素（已在上一个迭代中插入的元素），则只需将1添加到相应的值并更新哈希表条目（正确更新元素多重性）。最后，您的哈希表最多包含$ n $条目（这对应于链接列表中的元素不同的情况）或小于$ n $元素，其中至少一个显示了一个显示多重性的条目大于一个。这需要$ o（n）$时间，因为在$ n $迭代中，在哈希表上完成的工作为$ o（1）$。

2）现在，遍历哈希表并通过为每个元素添加一个节点来构建一个新的链接列表。这最多需要$ o（n）$，因为哈希表最多包含$ n $元素，因此在哈希表的每个元素上完成的工作为$ o（1）$，并在新列表中添加节点为$ o o （1）$。

因此，总复杂性最多为$ o（n）$。