找出数组中的重复元素
存在大小为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包含duplicate元素，但是使用这个方法我无法找到重复元素的索引。 为此，我需要再次遍历数组，这是不可取的。 任何人都可以提出一个更好的解决方案，不涉及添加方法或XOR方法在O（n）中工作？
根据问题描述的限制，您可以通过多种方式考虑此问题。
如果你知道一个元素是重复的 ，那么有很多方法可以解决这个问题。 一个特别聪明的解决方案是使用按位XOR运算符。 XOR具有以下有趣的属性：
- XOR是关联的，所以（x ^ y）^ z = x ^（y ^ z）
- XOR是可交换的：x ^ y = y ^ x
- XOR是它自己的逆：x ^ y = 0 iff x = y
- XOR的身份为零：x ^ 0 = x
这里的属性（1）和（2）意味着当获取一组值的XOR时，将XOR应用于元素的顺序无关紧要。 您可以根据需要对元素重新排序或分组。 属性（3）意味着如果你多次对同一个值进行异或运算，你就会返回零，而属性（4）意味着如果你对任何0进行异或，你就会得到原始数字。 将所有这些属性组合在一起，就会得到一个有趣的结果：如果你取一组数字的XOR，结果就是组中出现奇数次的所有数字的异或。 这样做的原因是，当您将出现偶数次数的XOR组合在一起时，您可以将这些数字的XOR分解为一组对。 每对XOR为0乘以（3），并且所有这些零的组合XOR通过（4）返回零。 因此，甚至多重性的所有数量都抵消了。
要使用它来解决原始问题，请执行以下操作。 首先，将列表中的所有数字进行异或。 这给出了所有出现奇数次数的XOR，除了重复之外，最终是从1到（n-1）的所有数字。 现在，将此值与从1到（n-1）的所有数字的XOR进行异或。 然后，这使得之前未被取消的1到（n-1）范围内的所有数字都被抵消，只留下重复的值。 此外，这在O（n）时间内运行并且仅使用O（1）空间，因为所有值的XOR适合单个整数。
在您的原始post中，您考虑了一种替代方法，该方法通过使用从1到n-1的整数之和为n（n-1）/ 2的事实。 但是，您担心这会导致整数溢出并导致问题。 在大多数机器上你是对的，这会导致溢出，但是（在大多数机器上）这不是问题，因为算术是使用固定精度整数完成的，通常是32位整数。 当发生整数溢出时，得到的数字不是没有意义的。 相反，它只是你计算实际结果时得到的值，然后除了最低32位之外的所有内容。 从数学上讲，这称为模运算，计算机中的操作以模232完成。 但更一般地说，假设整数以k为模数存储，用于某些固定的k。
幸运的是，你知道并且喜欢普通算术的许多算术法仍然适用于模运算。 我们只需要更准确地使用我们的术语。 我们说如果x和y在除以k时留下相同的余数，则x与y modulo k（表示为x≡ky）一致。 这在物理机器上工作时很重要，因为当大多数硬件上发生整数溢出时，结果值与模值k的真值一致，其中k取决于字大小。 幸运的是，以下定律适用于模运算：
例如：
- 如果x≡ky且w≡kz，则x +w≡ky + z
- 如果x≡ky且w≡kz，则xw≡kyz。
这意味着如果你想通过查找数组元素的总和并减去预期的总数来计算重复值，即使存在整数溢出，一切都会正常工作，因为标准算法仍会产生相同的值（模k）在硬件中。 也就是说，您也可以使用基于XOR的方法，它根本不需要考虑溢出。 🙂
如果不能保证只复制一个元素，但是你可以修改元素数组，那么有一个漂亮的算法可以找到重复的值。 这个早期的SO问题描述了如何实现这一目标。 直观地说，我们的想法是你可以尝试使用存储桶排序对序列进行排序 ，其中元素数组本身也被循环使用以保存存储桶的空间。
如果不能保证只复制一个元素，并且无法修改元素数组，那么问题就更难了。 这是一个经典（而且很难！）的面试问题据报道，Don Knuth需要24小时才能解决。 诀窍是通过将数组作为函数从数字1-n处理到1-（n-1），然后查找该函数的两个输入，将问题减少到循环查找的实例。 然而，最终的算法，称为Floyd的循环寻找算法 ，非常漂亮和简单。 有趣的是，它与用于在线性时间和恒定空间中检测链表中的循环的算法相同。 我建议查阅，因为它定期出现在软件访谈中。
有关算法的完整描述以及分析，正确性certificate和Python实现，请查看解决此问题的此实现 。
希望这可以帮助！
添加元素非常精细，在计算元素总和和预期总和时，只需要取中间聚合的mod（％）即可。 对于mod操作，您可以使用类似2n的内容。 您还必须在减法后修复该值。