###### tags: `Leetcode` `medium` `bit` `python` `c++`

# 260. Single Number III

## [題目連結:] https://leetcode.com/problems/single-number-iii/description/

## 題目:
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.

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

**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]

## 解題想法:
* 給一數組中，每個數都恰好兩個，只有兩個數皆只有出現一次
* 求該兩個數
* 只能用線性time、常數space
* Bit判斷:
* Step1:
* 將所有數xor **偶數的會全部消掉**

        mark=0
        for i in nums:
            mark ^= i

* Step2: **技巧**
* 最後得到的mark值為那兩個單一數的xor
* 用 **mark&(-mark)** 去判斷最低位為1者
* key = mark&(-mark)
* Step3: 再次遍歷整個數列
* 區分兩數為
* key&該數 = 0
* key&該數 = 1
* 將分類結果均進行xor

## Python:

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        #step1:將所有數xor 偶數的會全部消掉
        mark=0
        for i in nums:
            mark ^= i
        #step2:技巧: 最後得到的mark值為那兩個單一數的xor 
        #用mark&-mark去找到最低位為1者
        key = mark&(-mark)
        #區分兩數為與key& =0 or key& = 1
        res = [0,0]
        for n in nums:
            if (n&key)==0:
                res[0]^=n
            else:
                res[1]^=n
        return res

nums = [1,2,1,3,2,5]
result = Solution()
ans = result.singleNumber(nums)
print(ans)

## C++:
* 要用**unsigned int**，否則會runtime error
* runtime error: negation of -2147483648 cannot be represented in type 'int'

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unsigned int mark=0;
        for (int val:nums){
            mark^=val;
        }
        unsigned int key=(mark)&(-mark);
        vector<int> res(2,0);
        for (int val:nums){
            if ((val&key)==0)
                res[0]^=val;
            else
                res[1]^=val;
        }
        return res;
    }
};