假设我有一个包含 2n+2 个元素的数组。数组中的 n 个元素出现了两次，其余两个元素是唯一的。你必须在 O(n) 时间和 O(1) 空间内解决这个问题。解决方案之一是使用 XOR。但我无法理解这一点。任何人都可以帮助我解决这个问题或者可以给我更好的解决方案吗？
问题和解决方案的链接是this http://www.geeksforgeeks.org/archives/2457
首先 - 请注意a xor a == 0，对于每个a.
假设您有两个唯一的号码 -x,y.
如果对每个元素进行异或，最终会得到一个数字，等于x xor y（因为每个欺骗对都会使自己无效），并且至少有一位“向上”。选择这一位（如果有多个位，则选择哪一位并不重要），并将列表分成两个子列表：
(1) 设置了该位的所有数字。
(2) 该位未设置的所有数字。
其中一个唯一的数字有这个位，另一个没有（否则 - 它一开始就不是“向上”的），所以每个列表中有一个唯一的数字。
再次迭代每个列表，并对所有元素进行异或，结果是该列表中的唯一数字，因为每个重复对都会使自身无效。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
