algorithm - 我们如何在 O(n) 时间和 O(1) 空间复杂度内找到数组中重复的数字

Question

我们如何在 O(n) 时间和 O(1) 复杂度内找到数组中重复的数字？ 例如 数组 2,1,4,3,3,10 输出为 3

编辑: 我尝试了以下方式。 我发现如果 no 奇怪地重复，那么我们可以通过执行 xor 来实现结果。所以我想使奇数元素不重复甚至不重复，每个均匀重复不奇数。但为此我需要从 O(n) 中的输入数组中找出唯一的元素数组，但找不到方法。

Answer 1

假设数组中数字的值有一个上限(我用过的所有编程语言中的所有内置整数类型都是这种情况——例如，假设它们是 32 -位整数)有一个解决方案，使用常量空间:

1. 创建一个包含 N 个元素的数组，其中 N 是输入数组中整数值的上限，并将所有元素初始化为 0 或 false 或某些等效值。我将其称为lookup 数组。
2. 遍历输入数组，并使用每个数字索引查找数组。如果您找到的值为 1 或 true(等等)，则输入数组中的当前数字重复。
3. 否则，将查找数组中的相应值设置为1 或true，以记住我们已经看到了这个特定的输入数字。

技术上，这是 O(n) 时间和 O(1) 空间，并且它不会破坏输入数组。实际上，您需要事情按照您的方式进行才能让这样的程序实际运行(例如，如果在输入中谈论 64 位整数是不可能的)。