付費限定文章

二進位操作 尋找落單的數字 Single Number Leetcode #136 精選75題

題目在這裡:

題目敘述

題目會給定一個陣列，每個數字都恰好出現兩次，只有一個數字是例外。

要求我們找出那個落單也就是例外的數字。

測試範例

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 * 10^4

輸入陣列長度介於1~三萬。

• -3 * 10^ <= nums[i] <= 3 * 10^4

陣列元素值介於 負三萬 ~ 三萬

• Each element in the array appears twice except for one element which appears only once.

每個元素都恰好出現兩次，只有一個例外出現一次。

演算法

除了傳統的字典(雜湊表)去紀錄出現次數的做法以外，
其實還可以利用XOR對稱相消的特性來計算出答案。

Self-inverse :

A ⊕ A = 0

所有出現兩次的數字，再經過XOR計算後，都會剛好消去等於零。

只有落單、出現一次的那個數字，會殘留在最後的計算結果，也就是我們的最終答案。

程式碼