題目： LeetCode - 136. Single Number

題目說明

從一個陣列中找出不重複的數字。( 只會有一個數字不重複 )

解題思路

使用 XOR 位元運算，將 ans 先設為 nums[0]，再用一個迴圈從 1 開始，對 ans 做 XOR 位元運算，最後的結果即是答案。XOR 的介紹可以參考本篇文章：XOR 位元運算介紹。

為什麼要使用 XOR 呢？

因為 XOR 有一個特性是 A ^ A = 0，意思是當兩個相同的數字做 XOR 運算後會變成 0，而另一個特性是 A ^ 0 = A，意思是當任意一個數字對 0 做 XOR 運算後還是自己，恰巧很符合本題的題目，一個陣列內只有一個數字是單獨存在的，其他數字都會有兩個。那你可能會想說：可是陣列的順序不一定是 [A, A, B, B, C, C, D] 呀。這時就要提到 XOR 的第三個特性，A ^ B = B ^ A，就是說 XOR 其實是有交換律的，所以順序其實並不重要。這個題目其實也是 XOR 的經典題目，所有概念都有使用到。

參考解法

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = nums[0];
        for(size_t i = 1; i < nums.size(); ++i)
            ans ^= nums[i];
        return ans;
    }
};