问在O(1)空间中找到数组中的重复元素(数字不在任何范围内)

EN

让我们把重复的要素称为“多数”。

Boyer-Moore多数票算法在这里可以帮上忙。如果存在任何这样的元素，则该算法将查找输入中超过一半的元素重复出现的元素。

但就你的情况而言，情况很有趣。大多数可能发生的次数不超过一半。所有元素都是唯一的，除了重复的一个和重复的数字不相邻。此外，多数元素也确实存在。

所以,

1. 在数组中的偶数索引数字上运行多数投票算法。第二次遍历输入数组，以验证算法报告的元素确实占大多数。
2. 如果在上面的步骤中我们没有得到多数元素，您可以在数组中的奇数索引上重复上面的过程。您可以更聪明地执行第二步，因为我们确信大多数元素都存在。所以，任何重复的数字都是结果。

在上面的实现中，有一个很好的小优化空间。

我想我不应该在这里解释多数表决的算法。如果你想让我这么做，就告诉我。显然，在不知道这个多数算法的情况下，我们应该能够使用一些计数逻辑(这很可能会导致与多数算法相同的结果)。但这只是一个标准的算法，我们可以利用它。