arrays - 在数组中找到一个不重复的元素？

Question

我有一个n元素数组，其中只有一个元素不重复，否则所有其他数字都重复 >1 次。并且数组中的数字范围没有限制。

一些解决方案是：

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

有更好的解决方案吗？

Answer 1

如果您有严格的空间限制，请尝试多次扫描。

假设输入有 n 个元素，而你的记忆中只能保存 m 个元素。如果您使用哈希表方法，在最坏的情况下，您需要处理 n/2 个唯一数字，因此您需要 m>n/2。如果您没有那么大的 m，您可以将 n 个元素划分为 k=(max(input)-min(input))/(2m) 个组，然后继续扫描 n 个输入元素 k 次（在最坏的情况下）案子）：

第 1 次运行：您只使用 hash-get/put/mark/value < min(input)+m*2; 的任何元素；因为在 (min(input), min(input)+m*2) 范围内最多有 m 个唯一元素，您可以处理它。如果你很幸运，你已经找到了唯一的，否则继续。

第 2 次运行：仅对值在 (min(input)+m*2, min(input)+m*4) 范围内的元素进行操作，以此类推

通过这种方式，您将时间复杂度折衷为 O(kn)，但您会得到 O(m) 的空间复杂度界限

Answer 2

我想到了两个想法：

• 对于您的需要，平滑排序可能是比引用的合并排序更好的选择，因为它在内存使用方面是 O(1)，在最坏的情况下是 O(nlogn) 作为合并排序，但在最好的情况下是 O(n)；

• 基于展开树的（反向）想法，您可以制作一种树，一旦使用它们就会将叶子推向底部（而不是像展开树中那样向上）。这仍然会给你一个 O(nlogn) 植入，但优点是找到唯一元素的 O(1) 步骤，它将是根。排序算法是 O(nlogn) + O(n) 的总和，这个算法是 O(nlogn) + O(1)

否则，正如您所说，使用基于散列的解决方案（如散列实现集）将导致 O(n) 算法（O(n) 插入并添加计数引用并 O(n) 遍历您的集合找到独特的元素），但你似乎不喜欢内存使用，虽然我不知道为什么。内存很便宜，现在...

Answer 3

一种通用方法是实现一种分桶技术（其中散列技术就是这样一种技术），使用它们的标识（比如索引）将元素分配到不同的“桶”中，然后找到具有最小大小的桶（在您的情况下为 1）。我相信这个问题也被称为少数元素问题。集合中的独特元素将有多少桶。

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

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

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

您的问题似乎也与Element Uniqueness 问题松散相关。