刷題日記（9）Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

— — — -(solution中令人歎為觀止超聰明的解法)— — — — —

<Bit Manipulation>

Concept

• If we take XOR of zero and some bit, it will return that bit
• a⊕0=a

If we take XOR of two same bits, it will return 0

• a⊕a=0
• a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

So we can XOR all bits together to find the unique number.

意思就是只要使用xor最後剩下來的那個就是單獨的那個，因為已經兩兩消除了。

a^=i 是 a= a^i 的意思。

＾是XOR

Complexity Analysis

• Time complexity : O(n). We only iterate through nums, so the time complexity is the number of elements in nums.
• Space complexity : O(1).