#136. Single Number

題目描述

給你一個不是空的整數陣列，除了其中一個元素之外，每個陣列元素都會出現兩次，請找出只出現一次的元素。

你必須使用線性的執行時間以及不使用額外的空間。

限制條件

1 <= nums.length <= 3 * 10^4
-3 * 10^4 <= nums[i] <= 3 * 10^4
除了其中一個元素只會出現一次，其他每個元素都會出現兩次。
線性執行時間。
不使用額外空間。

解題思路

線性執行時間以及不使用額外空間這兩個限制阻止了我們使用Sorting和Hash Table來處理這個問題。

所以我們只能用互斥或(XOR)運算子來處理。

互斥或(XOR)運算子的邏輯如下：

＼	0	1
0	False	True
1	True	False

使用互斥或(XOR)運算時，兩個相同的數字，互斥邏輯成立，所以會變成0。而0與其他數字互斥或(XOR)運算時，或(OR)的邏輯成立，因此會得出的其他數字。

而這題會有三種組合，0、單數數字、一對數字，所有一對的數字都會互斥而被消除，剩下0和單數數字，所以當所有數字都使用互斥或(XOR)運算完後，就會剩下烙單的那個數字。

XOR

public class Solution { 
	public int SingleNumber(int[] nums) {
        int ans = 0;
        foreach(int i in nums){
            ans ^= i;
        }
        return ans;
    }
}

複雜度分析：

時間複雜度：線性時間O(n)。
空間複雜度：常數空間O(1)。

學習重點

互斥或(XOR)運算子。