嘿嘿～今天我們來聊一個超級有趣的小挑戰。
這個題目應該很適合那些常常覺得「為什麼總是我？」的朋友們～
哈哈，開玩笑的啦！題目是這樣的：
有一個整數陣列 nums，裡面的每個元素都出現兩次，除了那個倒楣鬼只出現了一次。

沒錯，我們的任務就是找出這個單身汪！但注意囉，我們不只要找到它，還得用線性時間複雜度，外加只能使用固定的額外空間。
這感覺就像是在找那根遺失的針，但放心！我們用 TypeScript 把它找出來！GO～

英文題目 Single Number

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

給定一個非空的整數陣列 nums，其中每個元素都出現兩次，只有一個元素只出現一次。找出這個出現一次的元素。

你必須實現一個線性時間複雜度的解法，並且只能使用固定的額外空間。

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

實作

function singleNumber(nums: number[]): number {
  let result = 0;

  for (let num of nums) {
    result ^= num; // XOR operation
  }

  return result;
}

解釋：

這邊的解法相當精簡巧妙，我們使用了 XOR（異或）運算符號。

XOR 的性質是：相同的數字異或後會得到 0，而任何數字與 0 異或則會保持不變。
這意味著，當我們把所有數字都 XOR 起來後，那些出現兩次的數字就會被互相抵消，只剩下出現一次的單身汪。

具體步驟：

1. 初始化變數 result 為 0。
2. 遍歷 nums 陣列中的每一個數字，用 XOR 把它們一一加到 result 中。
3. 最後 result 就是我們要找的那個只出現一次的數字。

解題脈絡：

這個題目看似簡單，但限制條件下要達成線性時間與固定空間複雜度，其實就是要把心思放在巧妙的運算上。用 XOR 來抵消重複的數字就剛好符合這個需求，既高效又不需要多餘的空間，真是物美價廉！

XOR 系列的運算符：

「XOR」是位元運算符（Bitwise Operators）中，特別是 ^（異或運算符）。
以下是與 XOR 系列相關的運算符以及它們的解釋：

1. ^ (XOR, 位元異或)

   • 意思：對兩個數字的每個位元進行 XOR（異或）操作。當兩個對應的位元相異時，結果為 1；當兩個位元相同時，結果為 0。
   • 用法範例：

     let a = 5;   // 0101 in binary
     let b = 3;   // 0011 in binary
     let result = a ^ b; // 0110 in binary, which is 6
     

   • 應用：通常用於找出唯一數字、交換變數值而不使用額外空間等。

2. & (AND, 位元且)

   • 意思：對兩個數字的每個位元進行 AND 操作。當兩個對應位元都為 1 時，結果為 1，否則為 0。
   • 與 XOR 的關聯：XOR 和 AND 常搭配用來進行進階的位元操作，例如遮罩或濾出某些特定位元。

3. | (OR, 位元或)

   • 意思：對兩個數字的每個位元進行 OR 操作。當兩個對應的位元中有至少一個為 1 時，結果為 1。
   • 與 XOR 的關聯：雖然 OR 與 XOR 在邏輯上不同，但兩者都屬於位元操作的一部分，用於多樣的邏輯處理。

4. ~ (NOT, 位元非)

   • 意思：反轉數字的所有位元（即 0 變 1，1 變 0）。
   • 與 XOR 的關聯：在進行 XOR 運算時，常需要配合 NOT 來反轉特定位元，以達到需要的效果。

XOR 運算的應用及特性：

• 去重：XOR 可以用來找出唯一存在的元素，如解題中的「找出單獨出現的數」。
• 交換數值：可以在不使用額外變數的情況下交換兩個數字的值：

  let a = 10, b = 20;
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
  // 現在 a = 20, b = 10
  

• 檢查兩個數是否相同：兩個數 XOR 結果為 0，表示數字相同。

本次要點：

• XOR 的性質：數字與自己 XOR 為 0，數字與 0 XOR 為自己。
• 線性時間與固定空間：XOR 操作讓我們輕鬆達成這兩個要求。
• 程式簡單明瞭：僅用幾行程式碼就能輕鬆解決，展示了運算符的強大。