題目：

官網題目連結

根據題目敘述，會給一個非空陣列 A，包含了 N 個整數，索引從 0 開始。N 為奇數，其中除了唯一一個元素之外，其他每個元素都可以與陣列中另一個有相同值的元素配對，目的就是找出這個無法配對的元素。
例如輸入 A=[9, 3, 9, 3, 9, 7, 9]，答案應為 7。

  • N 為範圍 [1~1000000] 的奇數。
  • 陣列 A 的每個元素都是 [1~1000000000] 範圍內的整數。

解法：

光看題目第一時間其實想到 LeetCode 的 20. Valid Parentheses，那時是用 stack 解的，不過這題並沒有那麼複雜，不需要考慮開關符號的問題。

再來會想到的是記憶法，用數字種類當索引，用出現次數當值。當初會這樣想是因為題目的範例暗示了同個數字是可以出現超過 2 次的，於是潛意識想要知道每種數字出現幾次，這樣的優點是可以在時間和複雜度 O(N) 的情況下獲得完整資訊。

寫到一半才想到，目的只是要回傳那個沒有重複的值啊，我多做那麼沒用的事情幹嘛!

於是目標會希望改成只對 A 遍歷 1 次，且減少空間的用量，這時候就會發現我並不需要紀錄每種數字出現幾次，反正出現重複的就刪掉就好，因此空間用量值只會需要一個回傳陣列。
由於會需要知道回傳陣列是否已包含當前遍歷到的值，你仍需要以數字種類當索引才能保持每次查找的時間複雜度是 O(N)。
可以複習一下我的另一篇文章 : PHP Array

時間和空間複雜度是一個估算用的參考，所以不管有沒有記憶數字出現幾次都是 O(N)，但身為工程師你應該會很清楚實際上到底程式執行的細節是什麼，以及當我的函式/方法已定義好要做 X，就不要浪費資源去多做用不到的 Y。

  • 時間複雜度 O(N)
  • 空間複雜度 O(N) – 實際上最多存到 (N/2)+1，因為已保證只有一個元素不重複

PHP 程式碼：