从列表中删除重复元素的最有效方法

Question

我有一个未排序的列表，我想从中删除重复项。在C中执行此操作最有效。在我的例子中，列表是一个链接的数组列表。换句话说，几个数组连接在一起。重复只能发生在不同的阵列中。因此，例如阵列1中不能有重复，但在阵列1和2中可以找到相同的编号。

Answer 1

这基本上是对Element Distinctness Problem的修改。链接经历了几种可能的解决方案。

一个常见而简单的解决方案是对列表进行排序并对排序列表进行传递，删除任何重复项。这会给你一个O（n * log（n））算法

如果你使用散列表，你可以做得更好（O（n））。浏览数组，将每个元素插入散列表中。如果遇到碰撞，您可能已经找到了重复，并且可以对这两个元素进行快速比较。