在数组中找到一个非重复元素？

Question

我有一个n元素数组,其中只有一个元素不重复,否则所有其他数字重复> 1次.并且对阵列中的数字范围没有限制.

一些解决方案是:

• 利用散列,但这会导致线性时间复杂度,但空间复杂度非常差
• 使用MergeSort 对列表进行排序O(nlogn),然后找到不重复的元素

有更好的解决方案吗？

Answer 1

一种通用方法是实现存储桶技术（其中散列就是这样一种技术），使用元素的标识（例如索引）将元素分配到不同的“存储桶”中，然后找到具有最小大小的存储桶（在您的例子中为 1）。我认为这个问题也被称为少数元素问题。您的套装中有多少个独特元素，就有多少个桶。

由于冲突以及您的算法如何处理冲突，通过散列来执行此操作是有问题的。某些关联数组方法（例如尝试和可扩展散列）似乎不适用，因为它们更适合字符串。

上述的一种应用是并查数据结构。您的集合将是存储桶，您需要为数组中的每个元素调用 MakeSet() 和 Find()，每次调用的成本为 $O(\alpha(n))$，其中 $\alpha(n) $ 是增长极其缓慢的阿克曼反函数。您可以将其视为有效的常数。

当元素已经存在时，您必须执行 Union。通过一些更改来跟踪具有最小基数的集合，此解决方案应该可行。该解决方案的时间复杂度为$O(n\alpha(n))$。

您的问题似乎也与元素唯一性问题松散相关。