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

Question

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

Answer 1

这基本上是对Element Distinctness Problem的修改。该链接通过几种可能的解决方案。

一种常见且简单的解决方案是仅对列表进行排序并通过排序列表，删除任何重复项。这将为您提供 O(n*log(n)) 算法

如果您使用哈希表，您可以做得更好（O（n））。遍历数组，将每个元素插入到哈希表中。如果发生碰撞，您可能已经找到了重复项，您可以对这两个元素进行快速比较。