查找给定数组中的重复和缺失数字

Question

对于包含从1到N的数字的给定数组A，我想找到重复和缺失的数字对（x，y）。实施例A = [1,3,3]，然后x = 3，y = 2。

虽然我知道这个问题可以通过采取这里提到的xor方法https://stackoverflow.com/a/5767648/5031518来解决。我无法理解解决方案的最后部分，其中x和y的值是通过基于设置位拆分数组从x ^ y中提取的。

如果有人能解释为什么两个列表的xor分别导致x和y的值，那将会很有帮助。

Answer 1

在第一阶段，您可以计算全范围1..N和列表中的xor值

1  2  3 .. x .. N  
1  2  3 ..   .. N  y

所有配对项的xor给出0，因此结果是p = x xor y

值p不为零，但设置了什么位？那些不同的x和y。

所以我们可以从p找到任何1位，称之为mask，并对值1..N和列表执行相同的过程，只选择具有此位设置的值

for all v in 1..N and in list:   
   if ((v & mask) == mask):
       newxor ^= v

毕竟，newxor包含或x或y（参与此处的所有其他项目都已配对），我们可以找到另一个项目

 xy = p ^ newxor

注意：我们无法区分重复的项目和遗漏的内容，只需获得一对。

以你为榜样

p = 1^2^3^1^3^3 = 1 = 001 binary

用面具001b重复程序只涉及奇数

 newxor = (1 xor 3) xor (1 xor 3 xor 3) = 3

剩下的号码是

 3 xor 1 = 2

例如(1,2,2)我们得到相同的p

p = 1^2^3^1^2^2 = 1 = 001 binary

和相同的newxor = 3和相同的休息值xy=2