[LeetCode 260] Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

• 1. The order of the result is not important. So in the above example, [5, 3] is also correct.
• 1. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Diffculty
Medium

Similar Problems
[LeetCode 136] Single Number Easy [LeetCode 137] Single Number II Medium

Analysis

http://www.cnblogs.com/maples7/p/4483196.html 思路:

打怪打到系列第三级，又回到了跟 I 类似的情况，也就是相同的数字是偶数个，不同的是，这里面有两个“怪胎”。 很容易联想到 I 的解法，把所有数异或起来。但是异或之后我们得到的是我们想要的那两个数的异或值，如何把它们从异或中拆分开呢？

假设我们要找的这两个数为 a, b, 而 x = a ^ b。

首先，a 肯定不等于 b，那么说明它们的二进制位一定是不完全相同的，所以 x 肯定不为 0。 也就是说，a 与 b 一定存在“某一位”，使得在它们中的某个数中是 0，而在另一个数中是 1，这是他们之间的一个差别。 我们可不可以利用这个差别来把这两个数从 x 中揪出来呢？ 是可以的。

利用这个差别，我们可以将整个 nums 集合分成两个集合。一个集合中是这 “某一位” 为 0 的在nums中的所有数，假设为集合 A。而另一个集合是这 “某一位” 为 1 的在nums中的所有数。假设 a 的这 “某一位” 是 0 ，b 的 这个“某一位”是1，那么显然 a 在集合 A 中，b 在集合 B 中，这样问题就完全转化成了与 I 一样的两个子问题，于是可以得解。

关于具体的代码实现，还有一点说明：

我们如何找到这个 “某一位” 呢？理论上，只要是在这一位上 a与b的值不同，都可以合格的成为我们需要找的某一位。既然无更多限制，那我们肯定是找好找的某一位咯。 我们可以用很常规和易懂的方法去找，但一般而言，我们肯定是找最右边（低位）那边符合要求的“某一位”嘛。更进一步说，就是找到 x 中最低位的 1 嘛。那当然我们可以从最低位开始枚举每一位，直到找到我们需要找的那个“某一位”。

还有一种更trick利用位运算的办法：找到 x 中最低位的 1，仔细想想，这跟另外一个已经熟知的问题很像。 当我们统计某个数的二进制展开中1的个数的时候，我们使用了一个技巧，即用 n &= n - 1 每次来清除 n 中当前最右边的那个 1。 n-1 是把 n 的最低位的 1 变成 0，并且使更低位的 0 全部变成 1，然后异或一下就把 最低位的 1 及其更低位全部都变成了 0，即达到了“清除最低位的 1 的目的”。 （详见：统计二进制展开中数位1的个数的优化 优化解法1）

在这个地方，我们需要逆向思维，即 保留 最低位的1，并且最好使得其他位 都变成0，这样我直接与 nums 中的每一个数相与，就可以直接将它们分成 A 和 B 两个集合了。 逆向思维会是这样：

n-1 的过程其实是把 最低位 1 和 跟低位 都位反转 (Bit Flipping) 的过程，那我们这里 首先也将 n 的所有位反转得到 n'。 然后我们再把 n'+ 1。。。 Opps! What did we get?

我们发现 n'+1 相对于 n 而言，最低位的1及其更低位的0 都没变，而其他位（比 最低位1 更高的位）都反转了。 那此时如果用 n & (n'+1) 得到的便是 除 n 中最低位 1 继续为 1 以外，其他各位都为 0 的数了。 n' 如何求？当然我们可以直接取反。但是联合 n'+1 来看，各个位取反再加一，这不正是计算机中 “负数补码” 的表示方式！ 所以我们可以直接用 n &= -n 得到 “除 n 中最低位 1 继续为 1 以外，其他各位都为 0 的数”！ （注意正数的补码的补码是它本身，所以即便 n 本身是负数，-n是正数，但 -n 依然是求 n 的补码。） 完美！

class Solution:

# @param {integer[]} nums
# @return {integer[]}
def singleNumber(self, nums):
    diff = 0
    for e in nums:
        diff ^= e
    diff &= -diff
    ans = [0, 0]
    for e in nums:
        if diff & e != 0:
            ans[0] ^= e
        else:
            ans[1] ^= e
    return ans