[leetcode]260.隻出現一次的數字（3）

給定一個整數數組 nums，其中恰好有兩個元素隻出現一次，其餘所有元素均出現兩次。 找出隻出現一次的那兩個元素。你可以按 任意順序 傳回答案。

進階：你的算法應該具有線性時間複雜度。你能否僅使用常數空間複雜度來實作？

示例 1：

輸入：nums = [1,2,1,3,2,5]
輸出：[3,5]
解釋：[5, 3] 也是有效的答案。
           

示例 2：

輸入：nums = [-1,0]
輸出：[-1,0]
           

示例 3：

輸入：nums = [0,1]
輸出：[1,0]
           

提示：

2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
除兩個隻出現一次的整數外，nums 中的其他數字都出現兩次
           

思路：位運算

如果隻有一個不同的數字，即題[leetcode]136.隻出現一次的數字，從頭到尾周遊數組進行異或，成對出現的會兩兩抵消掉，最後剩下的就是隻出現了一次的數。

如果有兩個隻出現一次的數字，那麼我們可以将所有的數字分成兩組，使得：

1.兩個隻出現一次的數字在不同的組中。

2.相同的數字會被分到相同的組中。

分組政策：

1.對所有數字進行一次異或，會得到兩個出現一次的數字的異或值。

2.在異或結果中找見一位非0位，則說明在該位上，一個數字為0，一個數字為1。

3.根據這一位數字進行分組，若是相同的數字也可以由于該位全為0或全為1分到一組

4.在每個組内再次進行全部異或，得到兩個數字。

AC代碼（C++）

class Solution {
   public:
    vector<int> singleNumber(vector<int>& nums) {
        int temp = 0, len = nums.size();
        for (int i = 0; i < len; i++) {
            temp ^= nums[i];  //從頭到尾異或
        }
        int div = 1;  //記錄異或結果中第一位為1的位
        int a = 0, b = 0;
        while ((div & temp) == 0) {
            div <<= 1;  //左移一位
        }
        for (int i = 0; i < len; i++) {
            //該位為1的分一組，為0的分另外一組
            if (div & nums[i]) {
                a ^= nums[i];
            } else {
                b ^= nums[i];
            }
        }
        return vector<int>{a, b};
    }
};