在具有整数的数组中，一个值在数组中有两次。你如何确定哪一个？

Question

假设阵列具有1至1,000,000的整数。

我知道解决这个问题的一些常用方法：

1. 如果包括1到1,000,000之间的所有号码，找到数组元素的总和，并从总金额中减去（N * N + 1/2）
2. 使用哈希表（需要额外的内存）
3. 使用位图（更少的内存开销）

我最近碰到另一种解决方案来了，我需要一些帮助，在了解背后逻辑它：

保持一个基数累加器。你异或 的索引和索引值都累加器。

x^C^x == C在这里很有用，因为每个数字将会是 的两倍，除了那里有两次，这将出现3 次。 （x^x^x == x）和最终的索引，它会出现一次。 因此，如果我们用种子最终指数蓄电池，蓄电池的 终值将是在列表中的两倍。

如果有人能帮助我理解这种方法背后的逻辑（用一个小例子！），我将不胜感激。

Answer 1

假设你有一个蓄电池

int accumulator = 0; 

在你的循环的每一步，你XOR运算i和v，其中i是循环迭代的索引和v累加器在i个值阵列的位置。

accumulator ^= (i^v) 

通常情况下，i和v将是相同的号码，这样你最终会做

accumulator ^= (i^i) 

但i^i == 0，因此这将最终成为一个空操作，累加器的值将保持不动。在这一点上，我应该说，数字的排列顺序并不重要，因为XOR是可交换的，所以即使阵列洗牌，并在最后的结果，开始应该还是0（累加器的初始值） 。

现在，如果阵列中出现两次是多少？显然，这个数字在XORing中会出现三次（一次是索引等于数字，一次是数字的正常外观，另一次是额外的外观）。此外，其他数字之一只会出现一次（仅限其索引）。

此解决方案现在继续假设仅出现一次的数字等于数组的最后一个索引，换句话说，数组中的数字范围是连续的，并且从第一个索引开始处理（编辑：感谢CAF这个单挑评论，这是我脑子里真的，但写当我完全搞砸了）。有了这个（N只出现一次），作为一个给定的，考虑开始

int accumulator = N; 

有效地使N在异或再次出现两次。在这一点上，我们剩下的号码只出现两次，而只有一个号码出现三次。由于两次出现的数字将异或为0，所以累加器的最终值将等于出现三次（即一次额外）的数字。

Answer 2

逻辑是你只需要存储累加器值，只需要经过一次数组。这很聪明。

当然，这是在实践中的最佳方法取决于它有多少工作来计算异或，以及如何大的数组。如果数组中的值是随机分布的，那么使用不同的方法可能会更快，即使它使用更多的内存，因为在检查整个数组之前很可能会发现重复值。

当然，如果数组是排序开始，事情是相当容易的。所以这很大程度上取决于数值在整个数组中的分布情况。

Answer 3

1个10001包括显示为一个数组索引之间的每个数字。 （是不是C数组0索引？那么，只要我们对数组值和索引都是从0开始还是从2开始都是一致的，它就没有什么区别。我将从数组开始1，因为这是这个问题似乎是说什么。）

无论如何，是的，1次10,001包出现，正是曾经之间的每一个数字，作为数组的索引。每个介于1和10,000之间的数字也仅以数组值出现一次，除了出现两次的重复值之外。所以数学上，我们正在做整体的计算如下：

1 xor 1 xor 2 xor 2 xor 3 xor 3 xor ... xor 10,000 xor 10,000 xor 10,001 xor D 

，其中d是重复的值。当然，计算中的术语可能不会按顺序出现，但xor是可交换的，所以我们可以重新排列我们喜欢的术语。对于每个n，n xor n为0。所以上面简化为

10,001 xor D 

xor this with 10,001 and you get D，the duplicated value。

Answer 4

问题是：你有兴趣知道如何做聪明但纯粹学术异或技巧与现实世界没有多大关联，或者你想知道这一点，因为在现实世界中，你可能会编写使用数组的程序？这个答案解决了后一种情况。

无废话的解决方案是要经过整个数组和你做排序。在排序时，确保没有重复值，即实现抽象数据类型“set”。这可能需要分配第二个数组，并且排序很耗时。无论它是多少少费时比聪明的异或技巧，我不知道。

然而，有什么好处ň未分类的值，你在现实世界中的数组？如果它们未排序，我们不得不假定它们的顺序很重要，所以原始数组可能不得不保存。如果你想搜索原始数组或者分析它的重复数，中间值等等，你真的想要它的一个分类版本。一旦你有了它，你可以用“O log n”进行二进制搜索。