題目敘述 Single Number III
給定一個輸入陣列，已知有兩個烙單的數字，其他剩餘的數字都恰巧出現兩次。
請找出這兩個烙單的數字。
題目額外提出限制，請使用O(n)線性時間、O(1)常數空間複雜度的演算法。測試範例
Example 1:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.
3和5就是烙單，只有出現一次的數字。
Example 2:
Input: nums = [-1,0]
Output: [-1,0]
Example 3:
Input: nums = [0,1]
Output: [1,0]
約束條件
Constraints:
2 <= nums.length <= 3 * 10^4
輸入陣列長度介於2~三萬之間。
-2^31 <= nums[i] <= 2^31 - 1
每個陣列元素都在4byte整數範圍內。
- Each integer in
numswill appear twice, only two integers will appear once.
只有恰好兩個數字烙單，其他剩餘的數字都剛好出現兩次。
觀察
如果最直覺的想法，就是用字典去記錄每個數字的出現次數。找出出現次數只有一次的數字即可。
演算法 二進位操作
但是，困難點在於題目多了額外拘束，限定使用O(1)常數空間。
可以怎麼做呢?
兩個烙單的數字代表兩個相異的數字，都只出現一次。
那麼，可以先找出兩個烙單數字相異的bit作為遮罩，
再用XOR過濾掉剩餘都出現兩次的數字(A XOR A = 0)，
最後留下來的數字，恰好就是那兩個烙單的數字。
程式碼 二進位操作
from functools import reduce
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = lambda x,y : x^y
xor_result = reduce( xor, nums)
# mask is the right-most 1 of xor result
# use mask to separate nums into two groups, one group contains single_num_a, the other contains single_num_b
mask = xor_result & -xor_result
single_num_a, single_num_b = 0, 0
for number in nums:
# separate and collect these two single numbers by masking
if mask&number:
single_num_a ^= number
else:
single_num_b ^= number
return [single_num_a, single_num_b]
複雜度分析
時間複雜度:O(n)
從左到右，掃描每個數字，每個數字計算一次。
空間複雜度: O(1)
使用到的都是固定尺寸的臨時變數，為常數級別O(1)。
