136. 只出現一次的數字

思路

亦或運算會讓出現偶數次的元素對消，將所有元素做亦或，就得到出現奇數的元素了。

程式碼

位運算

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int xor_all = 0;
        for(int& num : nums) {
            xor_all ^= num;
        }
        return xor_all;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$