在一个数组中找出重复的元素

Question

在一个数组中找出重复的元素

21

有一个大小为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)时间内可行？

- Poulami

1

这只是一个更简单的问题，与 在O(n)时间和O(1)空间中查找重复项 相比。 - caf

2

为此，我需要再次遍历数组，这是不可取的。为什么不可取呢？第二次遍历数组不会改变算法的复杂度。 - sepp2k

1

@caf：那里的解决方案修改了数组，这似乎在这里是不可取的。 - Wladimir Palant

@sepp2k：这不会改变复杂度，但它会使算法变慢（比如与单遍算法相比）。 - Nawaz

“diff contains the duplicate element”是什么意思？在最后，diff == (A[n-1] - (n-1))。那么sum有什么用呢？你没有在任何地方使用最终结果。 - Nawaz

2个回答

2

添加元素是完全可以的，只需要在计算元素和及预期和时对中间聚合进行模(%)运算。对于模运算，您可以使用类似2n的东西。您还需要在减法后修复值。

- Karoly Horvath

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

这是一种在线算法。我正在使用OP描述的元素求和解决方案，只是使用模算术，因此没有溢出。您知道1到n-1之间数字的总和。数组包含n个数字，其中一个元素重复，因此只需将它们相加，减去1->n-1的总和，就可以得到重复的数字。 - Karoly Horvath

啊，错过了“只有一个”部分，以为这是针对更一般的“某些元素重复”的情况。 - templatetypedef

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

根据您的问题描述的限制条件，您可以有许多方法来思考这个问题。

如果您确信只有一个元素是重复的，则有许多解决此问题的方法。其中一种特别聪明的解决方案是使用按位异或运算符。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时，应用XORs的顺序不重要。您可以重新排列元素或将它们分组。属性（3）意味着如果您多次XOR相同的值，则会得到零，属性（4）意味着如果您将任何内容与0 XOR，则会返回原始数字。综合所有这些属性，您将获得一个有趣的结果：如果您对一组数字进行XOR，则结果是该组中出现奇数次的所有数字的XOR。原因是当您对出现偶数次的数字进行XOR时，您可以将这些数字的XOR分解为一组对。每个对通过（3）XOR为0，所有这些零的组合XOR通过（4）返回零。因此，所有偶数重复的数字都会被取消。

为了解决原始问题，按照以下步骤进行。首先，对列表中的所有数字进行异或操作。这将给出所有出现奇数次的数字的异或值，最终是从1到（n-1）的所有数字，除了重复的数字。现在，将此值与从1到（n-1）的所有数字的异或值进行异或。这会使范围1到（n-1）中以前未被取消的所有数字都被取消，只留下重复的值。此外，由于所有值的异或值适合单个整数，因此此过程仅使用O（1）空间并在O（n）时间内运行。

在您的原始帖子中，您考虑了一种替代方法，该方法利用了从1到n-1的整数之和为n（n-1）/ 2的事实。但是，您担心这会导致整数溢出并引起问题。在大多数机器上，您是正确的，因为算术是使用固定精度整数（通常是32位整数）完成的。当整数溢出发生时，结果数字并不无意义。相反，它只是您计算实际结果后，删除除最低32位以外的所有内容得到的值。从数学上讲，这被称为模算术，并且计算机中的操作是模2 ³²完成的。更一般地说，假设整数存储在某个固定k模下。

幸运的是，许多你从普通算术中了解和喜爱的算术定律在模算术中仍然有效。我们只需要更加精确地使用术语。如果x和y被k整除时余数相同，我们说x模k同余于y（表示为x ≡_k y）。这在处理物理机器时非常重要，因为当大多数硬件发生整数溢出时，所得到的值在模k下与真实值同余，其中k取决于字长。幸运的是，在模算术中以下定律仍然成立：

例如：

1. 如果x ≡_k y且w ≡_k z，则x + w ≡_k y + z 2. 如果x ≡_k y且w ≡_k z，则xw ≡_k yz。

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

如果您不能保证只有一个元素重复，但可以修改元素数组，则有一种优美的算法可用于查找重复的值。这个早期的SO问题描述了如何实现。直观地说，想法是您可以尝试使用桶排序对序列进行排序，其中元素数组本身被循环利用来保存桶的空间。

如果您不能保证只有一个元素重复，且无法修改元素数组，则问题更加困难。这是一个经典的（而且难！）面试问题，据报道Don Knuth花费了24小时才解决。这个技巧是通过将数组视为从1-n的数字到1-（n-1）的函数的实例来将问题归约为cycle-finding。然后寻找该函数的两个输入。然而，得到的算法称为Floyd的循环查找算法，它非常简单易懂而又优美。有趣的是，它是在线性时间和恒定空间内检测链表中的循环所使用的相同算法。我建议您查找它，因为它经常出现在软件面试中。

如果您想了解完整的算法描述，以及分析、正确性证明和Python实现，请查看此实现来解决问题。

希望这可以帮助您！