題目連結:
題目意譯:
給定一個整數陣列 nums,除了其中兩個元素以外,其他每個元素都皆出現兩次。找到那個只出現一次的那兩個元素。你可以按任意順序回傳答案。
你的演算法應為線性時間複雜度並且使用常數大小的額外空間。
限制:
2 ≦ nums.length ≦ 3 × 10 ^ 4
-2 ^ 31 ≦ nums[i] ≦ 2 ^ 31 - 1
每個 nums 中的整數皆會出現兩次,除了某兩個整數以外。
範例測資:
範例 1:
輸入: nums = [1,2,1,3,2,5]
輸出: [3,5]
解釋: [5, 3] 也是一個合法的答案。
範例 2:
輸入: nums = [-1,0]
輸出: [-1,0]
範例 3:
輸入: nums = [0,1]
輸出: [1,0]
解題思維:
假設我們要求的兩個整數,一個值為 a、另一個值為 b。
接著我們把 nums 中所有數字 XOR 在一起(XOR 操作在
這題有介紹過),令其值為 X。因為 nums 中除了 a 、 b 以外都出現了兩次,因此根據 XOR 運算的特性,這些出現兩次的整數將會彼此抵銷。所以 X 之值為 a XOR b。
那麼接著我們要怎麼把它們分開呢?可以看到 a XOR b 基本上就是在求兩數字的每個位元的差異——如果對應位元不一樣,則該位元 XOR 結果即為 1;反之為 0。
所以我們在 X 隨便找一個是「1」的位元(我們知道 a ≠ b,所以必定可以找到至少一個),然後以那個位元為準回去 nums 中篩出那些該位元為「1」的整數。然後再對這些篩出來的整數再求一次 XOR 的結果,得 X'。此時的 X' 只會包含 a 或 b 其中一個數字(一如往常地,其他數字抵銷掉了)。
因此我們可以藉由 XOR 的特性得到另一個數字 X XOR X',因此 X' 和 X XOR X' 即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。