260. Single Number III

• 方法1:

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.

Example:

Input: [1,2,1,3,2,5]

Output: [3,5]

Note:

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

方法1:

水中的魚：http://fisherlei.blogspot.com/2015/10/leetcode-single-number-iii-solution.html

思路：

這題有兩個未知數，直接做異或肯定是不行的，那麼如何通過一些變換把這道題分解開，使得可以應用Single Number的解法來做，才是這個題目有意思的地方。

首先，對于數組A, 假設存在b，c兩個數字，在數組中隻出現了一次，那麼對于整個數組進行異或操作的話，

^ [A] = b^c , 因為其他的數因為出現了兩次，異或的過程中就被清零了。

但是僅僅通過最後異或出來的值，是沒辦法求出b和c的值的，但是足以幫我們把b和c劃分到不同的子數組中去。

一個整數有32位bit，對于b和c，除非兩者是相同的數，否則一定存在第K位bit，兩者是不同的。看下面的例子，

當找到這個K以後，就可以按照第K位bit是否等于1，将A數組劃分成兩個子數組，而這兩個子數組分别包含了b和c，那麼剩下的就隻需要把single number的算法直接應用到這兩個子數組上，就可以得到b和c了。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int num = 0;
        for (int a: nums) num ^= a;
        int i = 0;
        for (; i < 32; i++) {
            if (num & (1 << i)) break;
        }
        int a = 0, b = 0;
        for (int num: nums) {
            if (num & (1 << i)) a ^= num;
            else b ^= num;
        }
        return {a, b};
    }
};
           

grandyang: https://www.cnblogs.com/grandyang/p/4741122.html

進行 a &= -a 操作。首先變負數吧，在二進制中負數采用補碼的形式，而補碼就是反碼 +1，那麼 110 的反碼是 11…1001，那麼加1後是 11…1010，然後和 110 相與，得到了 10，就是代碼中的 diff 變量。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        diff &= -diff;
        vector<int> res(2, 0);
        for (auto &a : nums) {
            if (a & diff) res[0] ^= a;
            else res[1] ^= a;
        }
        return res;
    }
};