arrays - 是否可以在不使用任何数据结构的情况下找到数组中的第一个重复项，复杂度应小于或等于 O(n)

Question

If there is a random array say arr = [3, 5, 1, 4, 3] and N = 5 which indicates the size of the given array, is there a way to find the first repetitive value in the array (here the answer is 3) within O(N) time complexity but without using any data structure as a dictionary, map, tree, etc..But you can use a variable.

The idea is to have an optimal space complexity.

我在面试中被问到这个问题。

一般是用字典来解决，把数组的遍历项作为键，值作为计数。当我们的计数超过 2 时，我们就有了解决方案。但是如果我们不打算使用数据结构，那么我们必须在循环中循环以查找下一个项目。

我也想过只使用一个变量的解决方案，但一个变量是不够的。

我认为要在 O(N) 内得到解决方案是完全不可能的。但是，我可能是错的。请帮我找到解决方案。

已编辑

很抱歉之前没有提及此事。数组中的数字可以从 1 <= N 开始，即 1 <= arr[i] <= N

Answer 1

如果允许的话，一个简单的解决方案是对给定数组中的信息进行编码:

for (int i = 0; i < arr.length; i++) {
    int number = arr[i] < 0 ? -arr[i] : arr[i];
    if (arr[number - 1] < 0)
        // to restore the original array do:
        // for (j = 0; j < arr.length; j++) if (arr[j] < 0) arr[j] *= -1;
        return number;
    else
        arr[number - 1] = -arr[number - 1];
}

您可以再次修改数组(参见注释)，而不是立即返回解决方案，以便它与输入相同。如果临时修改也不可能，那么您可能需要使用排列循环。查看非常相似的问题:Find a duplicate in array of integers