查找数组中的重复元素

有一个大小为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）中工作吗？

来源

2011-08-19 Poulami

这只是* [查找O（n）时间和O（1）空间中的重复项]（http://stackoverflow.com/q/5739024/134633）* – caf

中的问题的一个简单情况。我需要再次遍历数组，这是不可取的“为什么不可取？第二次遍历数组不会改变算法的复杂性。 – sepp2k

@caf：那里的解决方案修改了这里看起来不太可取的数组。 –

根据问题描述的限制，您可以考虑很多方法来解决这个问题。

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

XOR是关联的，所以（X^Y）^ Z = X ^（Y^Z）
XOR是可交换的：X^Y = Y^x的
XOR是其本身的逆：X^Y = 0当且仅当x = y
XOR具有零作为同一性：X^0 = X

性能（1）和（2）在这里的意思是服用时将一组值与XOR进行XOR，将XOR应用于元素的顺序无关紧要。您可以对元素进行重新排序，或按照您认为合适的方式进行分组属性（3）意味着，如果你多次异或者相同的值，你会回到零，属性（4）意味着如果你与0异或，你会得到你的原始数字。综合所有这些属性，您会得到一个有趣的结果：如果您采用一组数字的XOR，则结果是组中出现奇数次的所有数字的异或。原因是，当你将偶数次出现的数字异或时，可以将这些数字的异或分解为一组对。每对通过（3）异或为0，并且所有这些零的组合XOR通过（4）返回零。因此，所有甚至多样性的数字都被抵消了。

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

在你原来的文章中，你考虑了一个替代方法，它使用从1到n-1的整数之和为n（n-1）/ 2的事实。但是，您担心这会导致整数溢出并导致问题。在大多数机器上，你是对的，这会导致溢出，但是（在大多数机器上）这不是问题，因为算术是使用固定精度整数完成的，通常是32位整数。当发生整数溢出时，结果数字不是没有意义的。相反，如果你计算出实际结果，它就是你得到的价值，然后放弃除最低32位之外的所有值。在数学上讲，这被称为模算术，并且计算机中的操作是以模2进行的。更一般地说，尽管如此，假设对于一些固定的k，整数是以模k存储的。

幸运的是，许多您熟悉并喜欢的算术法则仍然保留在模运算中。我们只需要用我们的术语更精确。我们说如果x和y除以k除以后的相同余数，那么x与y模k一致（表示为x ≡ _k y）。在物理机器上工作时这很重要，因为当大多数硬件发生整数溢出时，结果值与真值模k一致，其中k取决于字大小。幸运的是，下列法律持有真正的模块化的算术：

例如：

如果x ≡ _ķ Y和W ≡ _ķ Z，那么x + W ≡ _ķ Y + Z
如果x ≡ _ķ Y和W ≡ _ķ Z，然后XW ≡ _k yz。

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

如果你不能保证只有一个元素是重复的，但你可以修改元素数组，然后有一个美丽的算法来找到重复的值。 This earlier SO question描述如何完成这一点。直观的想法是，您可以尝试使用bucket sort对序列进行排序，其中元素数组本身也被循环使用以保存存储区的空间。

如果您不能保证只有一个元素被复制，并且您不能修改元素数组，那么问题就更加困难。这是一个经典的（而且很难！）面试问题，据报道，这个问题需要24小时解决。诀窍是将问题简化为cycle-finding的实例，方法是将数组作为函数从数字1-n拖到1-（n-1）上，然后查找该函数的两个输入。然而，由此产生的算法，名为，非常漂亮和简单。有趣的是，在线性时间和恒定空间中，您将使用相同的算法来检测链表中的周期。我建议您查看它，因为它会定期进行软件访谈。

对于具有分析性，正确性证明，以及Python实现算法沿的完整描述，请this implementation解决该问题。

希望这会有所帮助！

来源

2011-08-19 07:14:11 templatetypedef

一个有趣的注释：xor是与这些属性唯一的函数（达到同构）。换句话说，可数的无限组使得每个非同一元素都有二阶是同构的。有秩序的有限群体和每个非同一性元素的秩序2是同构的。 –

@ ChaoXu-你有参考我可以检查一下吗？另外，为什么不能证明无限数量的无限集？ – templatetypedef

对于有限情形，使用有限交换群的基本定理，我们有全部有限群，其中每个非同一元素的阶2同构于（Z_2）^ n对于某个n，而Z_2中的+与xor相同。（这表明这些组的顺序也必须是2^n）。对于可数无穷的情况，我写了一个使用小组演示文稿的证明：http://chaoxuprime.com/2011/06/countably-infinite-group-such-that-every-element-has-order-2-are- isomorphic –

添加元素非常好，您只需在计算元素总数和期望总和时使用中间聚合的mod（％）即可。对于mod操作，你可以使用类似2n的东西。减法后您还必须修复这个值。

来源

2011-08-19 09:23:52

你能详细说明一下吗？我对这个解决方案并不熟悉，不能完全告诉你想要做什么。你能发表更详细的算法和正确性证明吗？ – templatetypedef

这是一个在线算法。我使用OP描述的元素求和的总和，只是使用模算术，所以没有溢出。你知道从1到n-1的数字总和。该数组包含n个数字，重复一个元素，所以只需取其总和，减去总和1-> n-1，然后得到重复的数字。 –

啊，错过了“只有一个”的一部分，并认为这是对更普遍的“一些元素重复”的情况。 – templatetypedef

查找数组中的重复元素

回答

相关问题