这是一道面试题。
我得到了一个由范围在[1,n]内的n+1个整数组成的数组，该数组具有k (k≥1)个重复元素，每个重复元素可以出现多次。任务是以最佳时间和空间复杂度找到出现多次的数组元素。
经过长时间的思考，我自豪地提出了一个时间复杂度为O(nlogn)、空间复杂度为O(1)的解决方案。我的想法是将范围[1,n-1]分成两个部分，并确定哪个部分包含更多来自输入数组的元素（我使用了鸽笼原理）。算法继续递归执行，直到达到区间[X,X]，其中X出现两次，这是一个重复元素。
面试官很满意，但他告诉我存在一种具有恒定空间复杂度的O(n)解决方案。他慷慨地提供了几个提示（与置换有关？），但我不知道如何想出这样的解决方案。假设他没有说谎，有没有人能提供指导方针？我搜索了SO，找到了一些（更简单的）变体问题，但没有找到这个具体的问题。谢谢。
编辑：为了让事情变得更加复杂，面试官提到输入数组不应被修改。
取最后一个元素(x)。
保存位置x上的元素(y)。
如果x==y，则找到了重复项。
用x覆盖位置x。
将x=y赋值并继续执行第2步。
你基本上是在对数组进行排序，这是可能的，因为你知道要插入元素的位置。O(1)的额外空间和O(n)的时间复杂度。你只需要小心索引，为了简单起见，我在这里假设第一个索引是1（而不是0），所以我们不必进行+1或-1操作。
编辑：在不修改输入数组的情况下
该算法基于找到置换循环的入口点的想法，然后我们也找到了一个重复项（为了简单起见，再次使用基于1的数组）：
示例：
2 3 4 1 5 4 6 7 8
输入: 8 7 6
置换循环: 4 1 2 3
我们可以看到重复的数字(4)是循环的第一个数字。
找到置换循环
测量循环长度
找到置换循环的起始点
这3个主要步骤都是 O(n)，顺序执行，因此总体复杂度也是 O(n)，空间复杂度为 O(1)。
上面的例子:
x 取以下值: 8 7 6 4 1 2 3 4 1 2
a 取以下值: 2 3 4 1 2
b 取以下值: 2 4 2 4 2
因此 c = 4 (是的，有5个数字，但只有在进行步骤时才会增加c，而不是一开始就增加)
x 取以下值: 8 7 6 4 | 1 2 3 4
y 取以下值: | 8 7 6 4
最终 x == y == 4，这就是一个解！
第二个请求的示例: 3 1 4 6 1 2 5
进入循环: 5 1 3 4 6 2 1 3
测量循环长度:
a: 3 4 6 2 1 3
b: 3 6 1 4 2 3
c = 5
找到起始点:
x: 5 1 3 4 6 | 2 1
y: | 5 1
x == y == 1 是一个解
function checkDuplicate(arr) {
console.log(arr.join(", "));
let len = arr.length
,pos = 0
,done = 0
,cur = arr[0]
;
while (done < len) {
if (pos === cur) {
cur = arr[++pos];
} else {
pos = cur;
if (arr[pos] === cur) {
console.log(`> duplicate is ${cur}`);
return cur;
}
cur = arr[pos];
}
done++;
}
console.log("> no duplicate");
return -1;
}
for (t of [
[0, 1, 2, 3]
,[0, 1, 2, 1]
,[1, 0, 2, 3]
,[1, 1, 0, 2, 4]
]) checkDuplicate(t);这基本上是@maraca提出的解决方案（打字太慢了！）。它具有恒定的空间需求（对于局部变量），但除此之外，仅使用原始数组进行存储。在最坏情况下，它应该是O(n)，因为一旦找到重复项，该过程就会终止。
[1, 2, 1, 0]失败。 - giusti这要看你（你的应用）能使用什么工具。目前有很多框架/库存在。例如，在C++标准中，您可以使用std::map<>，就像maraca提到的那样。
或者如果您有时间，您可以自己实现二叉树，但需要记住插入元素与普通数组不同。在这种情况下，您可以优化搜索重复项，因为这可能在您的特定情况下是可能的。
O(n)的空间。 - Aurel BílýO(1)空间了。 - גלעד ברקן