在 O(1) space 中查找数组中的重复元素（数字不在任何范围内）

Question

给定一个包含 n 个整数的数组，所有数字都是唯一的，除了其中一个。

• 如果n为偶数，则重复数n/2次

• 如果n为奇数，则重复数重复(n-1)/2或(n+1)/2次

• 数组中重复数与自己不相邻

编写一个程序来查找重复数字而不使用额外的 space。

我就是这样解决问题的。

如果n是偶数，则有n/2个重复元素。此外，重复元素不应相邻。因此，如果说有 6 个元素，则重复 3 个元素。元素可以位于索引 0,2 和 4 或 1,3 和 5。因此，如果我只是检查是否有任何元素在索引 0 和 2 处重复，然后在索引 1 和 3 处重复，我可以获得重复元素。

如果n是奇数，那么有2个选择。

如果 (n+1)/2 个元素重复，那么我们可以只检查索引 0 和 2。例如有 7 个元素，其中 4 个重复，那么重复元素必须在索引 0 ,2,4 和 6.

但是，当 n 为奇数时，我找不到找到 (n-1)/2 个重复元素的方法。我想过使用 xor 和 sums 但找不到方法。

Answer 1

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

Boyer–Moore majority vote algorithm 可以提供帮助。如果存在任何这样的元素，该算法会找到一个元素，该元素对于输入的一半以上的元素重复出现。

但你的情况很有趣。大多数可能不会出现超过一半的次数。除了重复的元素和重复的数字不相邻外，所有元素都是唯一的。还有，多数元素是肯定存在的。

所以，

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

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

我想我不应该在这里解释多数表决算法。如果你想让我知道，请告诉我。显然，在不知道这种多数算法的情况下，我们应该能够使用一些计数逻辑来做到这一点（这很可能最终与多数算法相同）。但只是它是一个标准算法，我们可以利用它。