【LeetCode-136】136.隻出現一次的數字

隻出現一次的數字

給定一個非空整數數組，除了某個元素隻出現一次以外，其餘每個元素均出現兩次。找出那個隻出現了一次的元素。

說明：

你的算法應該具有線性時間複雜度。 你可以不使用額外空間來實作嗎？

參考思路：位運算

class Solution {
    // 使用位運算：數組中的全部元素的異或運算結果即為數組中隻出現一次的數字。
    // 時間複雜度O(n)，空間複雜度O(1)（線性時間複雜度）
    
    // 異或運算有以下三個性質：
    // 任何數和 0 做異或運算，結果仍然是原來的數，即 a⊕0=a。
    // 任何數和其自身做異或運算，結果是 0，即 a⊕a=0。
    // 異或運算滿足交換律和結合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
    
    public int singleNumber(int[] nums) {
        int ans = nums[0];
        if (nums.length > 1) {
           for (int i = 1; i < nums.length; i++) {
              ans = ans ^ nums[i];
           }
        }
        return ans;
    }
}