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

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

一些解决方案是：

有没有更好的解决办法？

2012-04-20 Luv

哈希表实际上并没有占用太多的空间：'O（n）'。如果数组太大以至于必须在原地进行，那么您可能需要使用外部排序。 – bdares 2012-04-20 05:01:55

散列的空间复杂度至多为'O（n）'（可能有'C> x'，对于一些小的'x'，取决于实现，尽管如此）。我喜欢“排序第一方法”。 – 2012-04-20 05:01:56

是的，但合并排序（就地）的空间复杂度为零。 – Thilo 2012-04-20 05:03:25

一种通用的方法是实现一种分段技术（其中散列法就是这样一种技术），使用它们的标识（比如索引）将元素分布到不同的“桶”中，然后找到最小尺寸的桶你的情况）。我相信这个问题也被称为少数族元素问题。将有尽可能多的水桶，因为你的设备中有独特的元素。

通过散列这样做是因为碰撞，以及如何你的算法可能会处理这个问题。某些关联数组方法（如try和可扩展哈希）似乎并不适用，因为它们更适合字符串。上述的

的一种应用是给Union-Find data structure。您的集合将成为存储桶，您需要为阵列中的每个元素调用MakeSet（）和Find（），每次调用的开销为$ O（\ alpha（n））$，其中$ \ alpha（n） $是非常缓慢增长的逆阿克曼函数。你可以把它看作是一个常数。

当元素已经存在时，你必须做联合。通过一些更改来跟踪基数最小的集合，该解决方案应该可以工作。该解决方案的时间复杂度为$ O（n \ alpha（n））$。

你的问题似乎也松散有关Element Uniqueness problem。

2012-04-20 17:53:40 rrufai

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

说输入有n个元素，你只能在你的记忆中保存m个元素。如果你使用散列表方法，在最坏的情况下，你需要处理n/2个唯一的数字，所以你需要m> n/2。如果没有那么大的m，可以将n个元素划分为k =（max（input）-min（input））/（2m）组，然后继续扫描n个输入元素k次（最差case）：

第一次运行：你只是散列/ get/mark /任何元素的值< min（input）+ m * 2;因为在范围内（min（输入），min（输入）+ m * 2），最多有m个独特元素，您可以处理它。如果你幸运的话，你已经找到了唯一的，否则继续。

第二运行：仅在范围内具有值元素进行操作（分钟（输入）+ M * 2，分钟（输入）+ M * 4），和等等，等等

以这种方式，你妥协的时间复杂度为O（KN），但你必然O（M）的空间复杂度

2012-04-21 22:30:06 HelloWorld

两个思路来我的脑海：

一个smoothsort可能比一个更好的选择所引用的mergesort为您的需要给出它在内存使用O（1），O（nlogn）在最差的cas e作为合并排序，但在最佳情况下为O（n）;
基础上splay tree的（反向）的想法，你可以做一个类型的树一旦被使用（而不是向上的伸展树），这将推动叶子朝底部。这仍然会给你一个O（nlogn）种类的植入，但好处将是寻找独特元素的O（1）步骤，它将是根。排序算法是O（nlogn）+ O（n）的总和，该算法将是O（nlogn）+ O（1）

否则，你说，使用基于散列溶液（如哈希实现的集合）会导致一个O（n）算法（O（n）插入并添加一个计数引用到它和O（n）遍历你的集合来找到唯一的元素），但你似乎不喜欢内存用法，但我不知道为什么。内存很便宜，这几天......

2012-05-15 05:04:25 Soravux

回答