給定一個數字數組nums，其中有兩個元素只出現一次，而其他所有元素均出現兩次。
找出這兩個只出現一次的元素。
例如：
給定nums = [1, 2, 1, 3, 2, 5]，返回[3, 5]。
備注：
1， 返回結果的順序不重要。所以在上例中，返回[3, 5]也是正確的。
2， 你的算法應該運行在線性時間復雜度。你可以只用常量空間復雜度來實現它嗎？
Given an array of numbers 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.
For example:
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
Note:
1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
本題我曾在《劍指Offer》中見過，記得要用位運算，自己實現了一遍，不過再看了看書上的，並沒有書上的規范，所以最後貼了書上的代碼……
其實有這麼一個性質：
任何數字異或其自身都等於零。
可能有讀者不了解什麼是異或，那麼就來插播一下：
異或，英文為exclusiveOR，或縮寫成xor，異或是一個被用於邏輯運算的數學符號。其數學符號是“⊕”，計算機符號是“xor”。
a⊕b=(?a∧b)∨(a∧?b)
true ⊕ false -> true
false ⊕ true -> true
true ⊕ true -> false
false ⊕ false -> false
也就是說兩個值相同則異或結果為假，兩個值不同則異或為真。所以任何數字異或其自身都等於零，因為兩個值相同。
好了，切入正題。就以題目中給出的數組為例吧：
[1, 2, 1, 3, 2, 5, 6, 5, 4, 6]
分別換算成二進制如下：
0001、0010、0001、0011、0010
0101、0110、0101、0100、0110
對所有數組進行異或運算得出的結果是：0111
於是進行分組如下：
A組： 0001（1）、0010（2）、0001（1）、0011（3）、0010（2）
B組： 0101（5）、0110（6）、0101（6）、0100（4）、0110（5）
對A組進行再次異或運算的結果是：0011（3）
對B組進行再次異或運算的結果是：0100（4）
判斷該數字的二進制第n位是否是1的函數：
bool IsBit1(int num, unsigned int index) {
num = num >> index;
return (num & 1);
}`
找出該數字二進制中第一個1的函數：
unsigned int FindFirstBigIs1(int num) {
int indexBit = 0;
while (((num & 1) == 0) && (indexBit < 8 * sizeof(int))) {
num = num >> 1;
++indexBit;
}
return indexBit;
}
根據LeetCode的函數模板修改了一點：
vector singleNumber(vector& nums) {
vector singleV;
if (nums.size() <= 0) return singleV;
int resultExclusiveOR = 0;
for (int i = 0; i < nums.size(); ++i)
resultExclusiveOR ^= nums[i];
unsigned int indexOf1 = FindFirstBigIs1(resultExclusiveOR);
int singleNum1 =0, singleNum2 = 0;
for (int j = 0; j < nums.size(); ++j) {
if (IsBit1(nums[j], indexOf1))
singleNum1 ^= nums[j];
else
singleNum2 ^= nums[j];
}
singleV.push_back(singleNum1);
singleV.push_back(singleNum2);
return singleV;
}
還有兩道相關的題：
LeetCode 136 Single Number（只出現一次的數字）
LeetCode 137 Single Number II（只出現一次的數字 II）（*）
