---
# System prepended metadata

title: 260. Single Number III
tags: [Leetcode, bit, medium, python, c++]

---

###### 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 **偶數的會全部消掉**
        ``` python=
        mark=0
        for i in nums:
            mark ^= i
        ```
    * Step2: **技巧**
        * 最後得到的mark值為那兩個單一數的xor 
        * 用 **mark&(-mark)** 去判斷最低位為1者
            * key = mark&(-mark)
    * Step3: 再次遍歷整個數列
        * 區分兩數為
            * key&該數 = 0 
            * key&該數 = 1
        * 將分類結果均進行xor

## Python:
``` 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'
``` cpp=
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;
    }
};
```