leetcode260 隻出現一次的數字

題目

260. 隻出現一次的數字 III

給定一個整數數組 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 中的其他數字都出現兩次
           

思路

下面兩個原則（重要）：

1. 任何數字與0異或得到數字本身；兩個相同的數字異或得0。依照這兩個原則，假如一個數組中，有一個元素隻出現一次，其他元素均出現兩次，那麼将數組中所有的數字異或即可得到隻出現一次的元素的結果。
2. z & (-z)得到的是z最低位為1的數：例如z為001100，那麼-z：z首先取反110011，然後加1，得到110100，z和-z相與得到100。

接着說下這道題怎麼解：

1. 将數組中所有的數進行異或，得到結果z。那麼z中的1位表示的是數組中兩個不同的數字之間不同的位。因為是兩個不同的數，是以一定至少存在一個不同的位。
2. 通過z&（-z）取最低位1的數，例如100，結果表示為y。
3. y可以将數組分成兩個子數組（規模不一定相同），做法是将y和數組中每個數進行相與，如果為0，則說明與y相與的數，和y最高位的1對應的是0；如果為1，則說明與y相與的數，和y最高位的1對應的是1。上述數組中兩個不相同的數，一定會劃分到不同的子數組中。将子數組中所有的數分别進行異或，兩個子數組最終得到的結果分别就是兩個不同的數。

時間複雜度： O ( N ) O(N) O(N)

空間複雜度： O ( 1 ) O(1) O(1)

class Solution {
    public int[] singleNumber(int[] nums) {
        int res = 0;
        for(int num : nums){
            res = res ^ num;
        }
        res = res & (-res);
        int[] arr = new int[2];
        for(int num : nums){
            if((num & res) == 0) {
                arr[0] ^= num;
            }else{
                arr[1] ^= num;
            }
        }
        return arr;
    }
}