假设我有一个包含 2n+2 个元素的数组。数组中的 n 个元素出现两次，其余两个元素是唯一的。你必须在 O(n) 时间和 O(1) 空间内解决这个问题。解决方案之一是使用 XOR。但我无法理解。任何人都可以帮助我或者可以给我更好的解决方案吗？
问题和解决方法的链接是这里
问问题
1550 次
1 回答
10
首先要注意的是a xor a == 0，对于每个a。
假设您有两个唯一的数字 - x,y。
如果你对每个元素执行异或，你最终会得到一个数字，它等于x xor y（因为每个欺骗对都会使自己无效），并且至少有一个“向上”位。选择这个位（如果有一个以上的位，你取哪个位无关紧要），并将列表分成两个子列表：
（1）设置了这个位的所有数字。
(2) 所有未设置此位的数字。
一个唯一编号有这个位，另一个没有（否则 - 它一开始就没有“向上”），所以每个列表中都有一个唯一编号。
再次迭代每个列表，并对所有元素进行异或，结果是该列表中的唯一编号，因为每个重复对都会使自己无效。
于 2012-08-07T10:00:59.353 回答