260. Single Number III

Medium

Given an integer array 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. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

Example 1:

Input: nums = [1,2,1,3,2,5]
Output:
 [3,5]
Explanation: 
 [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output:
 [-1,0]

Example 3:

Input: nums = [0,1]
Output:
 [1,0]

Constraints:

• 2 <= nums.length <= 3 * 104

• -231 <= nums[i] <= 231 - 1

• Each integer in nums will appear twice, only two integers will appear once.

解題

這題很技巧，我也是先看了別人的解答才寫的哈哈哈。

XOR 運算子：

A	B	Q
0	0	0
0	1	1
1	0	1
1	1	0

發現了嗎？當兩個數字相同時，彼此做 XOR 會抵銷變成 0 。而題目給的數字陣列中，除了答案需要的兩個數字只出現一次，其他數字都出現兩次。所以全部數字做 XOR 的結果，其實就是答案兩個數做 XOR 。

3 : 011

5: 101

3 XOR 5 : 110

如果我們取 010 作為 mask ，再對 3, 5 做 AND，5 會得到 0 ，而 3 不會，這時就可以區別並得出兩個數字。

func singleNumber(nums []int) []int {
    xor := 0
    num1, num2 := 0, 0

    for _, num := range nums {
        xor ^= num
    }
    mask := 1

    for xor & mask  == 0 {
        mask <<= 1
    }

    for _, num := range nums {
        if num & mask == 0{ //留下5
            num1 ^= num
        } else { //留下3
            num2 ^= num
        } // 其他數字會被抵消
    }

    return []int{num1, num2}
}