数组是否存在唯一元素？

Question

我正在寻找最高效的算法来检查数组中是否有唯一元素。结果不必是唯一元素，只需相应地返回 true 或 false。我知道可以使用哈希表或类似方法达到 O(n) 的效率，但我仍在寻找更加高效的空间利用率的结果。

例如- 数组无序，并且包含整数。

- josh

---

嗨，这个数组包含整数。 - josh

是的，我忘记了补充。它是一个未排序的数组，谢谢。 - josh

不，两者都是不正确的。我想知道数组/是否有/唯一元素；它可以有几个唯一元素，但我只想知道它是否有一个。也就是说，该算法对于像{3,4,4,5}或{1,2,2}这样的数组是正确的，但对于{2,4,2,4}这样的数组是错误的。（编辑：看起来我回复的评论已被删除...） - josh

这些整数的范围是多少？如果您能保证整数可以有的不同值的数量为k，那么我可以为您提供一个简单的O(n)时间复杂度，O(k)空间复杂度的算法。 - David Grayson

Answer 1

如果可能的值的数量很小并且事先已知，你可以使用位数组（时间复杂度为O(n)，空间复杂度为O(n)，比哈希表所需的空间更少）。

如果可能的值的数量很大，并且您需要这个过程是确定性的，那么您可以使用哈希表（如果您有一个良好的哈希函数并且不需要扩展哈希表，则时间复杂度为O(n)），或者就地排序列表（排序的时间复杂度为O(n * lg(n))，加上搜索第一个唯一元素的O(n)）

如果可能的值的数量很大，您不需要这个过程是确定性的，并且如果要查看特定元素是否在集合中，您也可以使用Bloom Filter。 Bloom Filter比哈希映射更节省空间，但存在误判的概率（数据结构认为元素在集合中，但实际上不在）

- NamshubWriter

---

我没有听说过 Bloom 过滤器，但它肯定听起来很有趣。谢谢。 - josh

Answer 2

我不确定O(n)，但使用O(n^2)可以取一个元素并将其与其他元素异或。

- Neel Basu

---

如果有偶数个非唯一元素，则异或运算将给出唯一的元素。 - kefeizhou

如果你对O(n^2)算法感到满意，那么你可以将每个元素与其他每个元素进行比较。虽然空间复杂度为O(1)，哈哈。 :-) - davidg

Answer 3

在 PHP 中有一个名为 array_keys() 的函数。

array array_keys ( array $input [, mixed $search_value [, bool $strict = false ]] )

如果设置了可选参数$search_value，则函数仅返回找到的值的键。如果只有一个数组键返回，那么该值必须是唯一的。

我猜我的答案有点太（语言）特定了，而且我不知道这个函数的大O。你必须自己测试它。 :)

[更新]: 我发现this article描述了array_keys()的O(n)。

- derphil

Answer 4

有三种不同的方法，具有不同的空间和时间复杂度：

1）两个循环：时间O(n^2)，空间O(1)。

2a）排序然后线性检查：一般情况下时间复杂度为O(nlogn)，空间复杂度为O(1)。 2b）非比较排序（基数、计数等）然后检查：时间O(n)，空间O(n)

3）哈希表或数组存储成员资格：时间O(n)，空间O(n)。

因此，基本上你应该选择2a（空间限制）或3。

- Binh Nguyen