找出数组中重复的元素

有一个大小为 n 的数组，数组中包含的元素在 1 到 n-1 之间，每个元素出现一次，只有一个元素出现多次。我们需要找到这个元素。

尽管这是一个非常常见的常见问题解答，但我仍然没有找到正确的答案。大多数建议是我应该将数组中的所有元素相加，然后从中减去所有索引的总和，但如果元素数量非常大，这将不起作用。它会溢出。还有关于使用异或门的建议dup = dup ^ arr[i] ^ i，我不清楚。

我想出了这个算法，它是加法算法的增强，将在很大程度上减少溢出的机会！

for i=0 to n-1
  begin :
    diff = A[i] - i;
    sum  = sum + diff;
  end

diff包含重复元素，但使用此方法我无法找到重复元素的索引。为此，我需要再次遍历数组，这是不可取的。谁能想出一个更好的解决方案，不涉及加法或 XOR 方法在 O(n) 中工作？

您可以通过多种方式来思考这个问题，具体取决于问题描述的限制。

如果您确实知道有一个元素是重复的，那么解决这个问题的方法有很多种。一种特别聪明的解决方案是使用按位异或运算符。 XOR 具有以下有趣的属性：

1. XOR 是结合律，因此 (x ^ y) ^ z = x ^ (y ^ z)
2. XOR 是可交换的：x ^ y = y ^ x
3. XOR 是它自己的逆： x ^ y = 0 iff x = y
4. XOR 以零作为恒等式：x ^ 0 = x

这里的属性 (1) 和 (2) 意味着当对一组值进行异或时，将异或应用于元素的顺序并不重要。您可以根据需要对元素重新排序或分组。属性 (3) 意味着，如果对相同的值进行多次异或，则会返回零，而属性 (4) 意味着，如果将任何值与 0 进行异或，则会返回原始数字。将所有这些属性放在一起，您会得到一个有趣的结果：如果对一组数字进行异或，则结果是该组中出现奇数次的所有数字的异或。这样做的原因是，当您将出现偶数次的数字异或在一起时，您可以将这些数字的异或分解为一组对。每对通过 (3) 与 0 进行异或，所有这些零的组合异或通过 (4) 返回零。因此，所有偶重数的数字都相互抵消。

要使用它来解决原始问题，请执行以下操作。首先，将列表中的所有数字异或在一起。这给出了所有出现奇数次的数字的异或，最终得到从 1 到 (n-1) 的所有数字，除了重复的数字。现在，将此值与从 1 到 (n-1) 的所有数字的 XOR 进行异或。然后，这会使之前未取消的 1 到 (n-1) 范围内的所有数字取消，只留下重复的值。此外，它的运行时间为 O(n)，并且仅使用 O(1) 空间，因为所有值的 XOR 都适合单个整数。

In your original post you considered an alternative approach that works by using the fact that the sum of the integers from 1 to n-1 is n(n-1)/2. You were concerned, however, that this would lead to integer overflow and cause a problem. On most machines you are right that this would cause an overflow, but (on most machines) this is not a problem because arithmetic is done using fixed-precision integers, commonly 32-bit integers. When an integer overflow occurs, the resulting number is not meaningless. Rather, it's just the value that you would get if you computed the actual result, then dropped off everything but the lowest 32 bits. Mathematically speaking, this is known as modular arithmetic, and the operations in the computer are done modulo 2³². More generally, though, let's say that integers are stored modulo k for some fixed k.

Fortunately, many of the arithmetical laws you know and love from normal arithmetic still hold in modular arithmetic. We just need to be more precise with our terminology. We say that x is congruent to y modulo k (denoted x ≡_k y) if x and y leave the same remainder when divided by k. This is important when working on a physical machine, because when an integer overflow occurs on most hardware, the resulting value is congruent to the true value modulo k, where k depends on the word size. Fortunately, the following laws hold true in modular arithmetic:

例如：

1. If x ≡_k y and w ≡_k z, then x + w ≡_k y + z
2. If x ≡_k y and w ≡_k z, then xw ≡_k yz.

这意味着，如果您想通过查找数组元素的总和并减去预期总数来计算重复值，即使存在整数溢出，一切都会正常进行，因为标准算术仍然会产生相同的值（模 k）在硬件中。也就是说，您也可以使用基于 XOR 的方法，它根本不需要考虑溢出。 :-)

如果不能保证恰好有一个元素重复，但可以修改元素数组，然后有一个漂亮的算法来查找重复值。这个较早的问题 https://stackoverflow.com/questions/5739024/finding-duplicates-in-on-time-and-o1-space/5739336#5739336描述了如何实现这一点。直观地说，这个想法是您可以尝试使用桶排序 http://en.wikipedia.org/wiki/Bucket_sort，其中元素数组本身也被回收以保存存储桶的空间。

如果不能保证恰好有一个元素是重复的，并且无法修改元素数组，那么问题就困难得多。这是一个经典（而且很难！）的面试问题，据说 Don Knuth 花了 24 小时才解决。诀窍是将问题简化为一个实例周期发现 http://en.wikipedia.org/wiki/Cycle_detection通过将数组视为从数字 1-n 到 1-(n-1) 的函数，然后查找该函数的两个输入。然而，生成的算法称为Floyd 的环路查找算法 http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare，极其美丽和简单。有趣的是，它与用于检测线性时间和恒定空间中链表中的循环的算法相同。我建议您查阅一下，因为它会定期出现在软件采访中。

有关算法的完整描述以及分析、正确性证明和 Python 实现，请查看这个实现 http://keithschwarz.com/interesting/code/?dir=find-duplicate这解决了问题。

希望这可以帮助！