在数组中找出重复的元素

  • Z时代
  • 2024-01-10
  • 分类：问答

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

尽管这是一个非常常见的问题，但我仍然没有找到正确的答案。大多数建议是，我应该将数组中的所有元素加起来，然后从中减去所有索引的总和，但是如果元素的数量很大，这将不起作用。它将溢出。还有一些关于使用XOR门的建议，这些建议对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运算符。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）表示，当对一组值进行XOR运算时，将XOR应用于元素的顺序无关紧要。您可以根据需要重新排列元素或对其进行分组。属性（3）表示如果多次对同一个值进行XOR，则返回零，而属性（4）表示如果对0与任何值进行XOR，则将返回原始数字。将所有这些属性加在一起，会得到一个有趣的结果：如果对一组数字进行异或运算，结果就是该组中所有出现奇数次的数字的异或运算。这样做的原因是，当您对出现偶数的数字进行XOR运算时，可以将这些数字的XOR分解为一组对。每对XOR乘以（3）等于0，所有这些零的组合XOR则返回零乘以（4）。所以，

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

在您的原始文章中，您考虑了一种替代方法，该方法通过使用从1到n-1的整数之和为n（n-1）/

2的事实起作用。但是，您担心这会导致整数溢出并引起问题。在大多数机器上，这会导致溢出是正确的，但是（在大多数机器上）这不是问题，因为算术是使用固定精度的整数（通常是32位整数）完成的。当发生整数溢出时，结果数并非没有意义。相反，它只是您计算实际结果然后除最低的32位之外的所有内容所获得的值。从数学上讲，这称为模块化算术，并且计算机中的运算以模2

32为模完成。。不过，更笼统地说，对于某些固定k，整数以k为模存储。

幸运的是，您从普通算术中学到的和喜欢的许多算术定律仍保留在模数算术中。我们只需要更加精确地定义我们的术语即可。我们说，如果x和y被k除以相同的余数，则x与y

模k一致（表示为x k

y）。这在物理机上工作时很重要，因为当大多数硬件上发生整数溢出时，结果值将取模k的真值，其中k取决于字长。幸运的是，以下定律在模块化算术中成立：

例如：

  1. 如果x k y和w k，则x + w k y + z

  2. 如果x≡ ķ Y和W≡ ķ Z，然后XW≡ ķ YZ。

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

那么可以使用一种漂亮的算法来查找重复的值。

这个较早的SO问题描述了如何完成此任务。直观地讲，您可以尝试使用bucketsort对序列进行排序，元素数组本身被回收以容纳buckets的空间。

那么问题就难得多。据报道，这是一个经典的（而且很困难！）面试问题，据说花了Don Knuth

24小时来解决。诀窍是通过将数组视为从数字1-n到1-（n-1）的函数，然后寻找该函数的两个输入，将问题简化为循环查找的情况。但是，所得的算法称为Floyd的循环查找算法，非常漂亮且简单。有趣的是，它与在线性时间和恒定空间中检测链表中的循环所使用的算法相同。我建议您查找它，因为它会定期出现在软件采访中。

有关算法的完整说明以及分析，正确性证明和Python实现，请查看解决问题的

。

希望这可以帮助！

以上是 在数组中找出重复的元素 的全部内容， 来源链接： utcz.com/qa/419329.html

回到顶部