我们怎样才能在 O(n) 时间和 O(1) 复杂度内找到数组中的重复数字？
例如
数组 2,1,4,3,3,10
输出为3
编辑：
我尝试了以下方式。
我发现如果 no 奇怪地重复，那么我们可以通过执行 xor 来实现结果。所以我想使奇数不重复到偶数不重复，并且每个均匀重复不重复到奇数。但是为此我需要从 O(n) 中的输入数组中找出唯一元素数组，但找不到方法。
假设数组中数字的值存在上限（我曾经使用过的所有编程语言中的所有内置整数类型都是这种情况 - 例如，假设它们是 32 位整数）有一个使用恒定空间的解决方案：
- 创建一个包含 N 个元素的数组，其中 N 是输入数组中整数值的上限，并将所有元素初始化为
0 or false或一些同等的东西。我将其称为lookup array.
- 循环输入数组，并使用每个数字来索引查找数组。如果你找到的值是
1 or true（等等），输入数组中的当前数字是重复的。
- 否则，将查找数组中的相应值设置为
1 or true请记住我们已经看到了这个特定的输入数字。
从技术上来说，这是 O(n) 时间和 O(1) 空间，并且不会破坏输入数组。实际上，您需要按照您的方式运行这样的程序（例如，如果在输入中谈论 64 位整数，则这是不可能的）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
