題目描述

給定一個非空的nums整數陣列,除了其中一個元素之外,其它的元素都重複出現了一次。找出單獨存在的那個元素。



您必須實作出線性時間複雜度的解答,且只能夠使用常數的額外空間複雜度。

原題網址

https://leetcode.com/problems/single-number/

輸入格式

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 陣列中除了其中一個元素之外,其它的元素都重複出現了一次。

輸出格式

單獨存在的那個整數數字。

範例輸入1

nums = [2, 2, 1]

範例輸出1

1

範例輸入2

nums = [4, 1, 2, 1, 2]

範例輸出2

4

範例輸入3

nums = [1]

範例輸出3

1

題解

這題其實利用#{{A \text{ xor } A = 0}}#和#{{A \text{ xor } 0 = A}}#這兩個邏輯式子就可以解答了。走訪陣列所有的元素,並元素值全都#{{\text{xor}}}#起來,最後的值就是那個單獨存在的元素值。

參考答案