我们如何在O（n）时间和O（1）空间复杂度中找到数组中的重复数
我们如何才能以O（n）时间和O（1）复杂度在数组中找到重复的数字？例如数组2,1,4,3,3,10输出为3
编辑：我尝试以下方式。我发现，如果奇怪地重复否，那么我们可以通过做xor来达到结果。所以我想使奇数元素不重复甚至不重复，每个均匀重复不重复到奇数。但是为此我需要从O（n）的输入数组中找出唯一的元素数组，但找不到路。
回答：
假设数组中的数字值有一个上界（我曾经用过的所有编程语言中的所有内置整数类型都是这种情况—例如，假设它们是32位整数）有一个使用常量空间的解决方案：
- 创建一个由N个元素组成的数组，其中N是输入数组中整数值的上限，并将所有元素初始化为
0或false等效。我将其称为 查找 数组。 - 循环输入数组，并使用每个数字索引到查找数组。如果找到的值是
1或true（等），则输入数组中的当前数字是重复的。 - 否则，将查找数组中的相应值设置为
1或true记住我们已经看到了这个特定的输入数字。
从技术上讲
，这是O（n）时间和O（1）空间，并且不会破坏输入数组。实际上，您需要采取各种措施才能真正运行这样的程序（例如，在输入中谈论64位整数是不可能的）。
以上是 我们如何在O（n）时间和O（1）空间复杂度中找到数组中的重复数 的全部内容， 来源链接： utcz.com/qa/418915.html
