題目敘述 Single Number II
給定一個輸入陣列，已知有一個烙單的數字，其他剩餘的數字都恰巧出現三次。
請找出這個烙單的數字。
題目額外提出限制，請使用O(n)線性時間、O(1)常數空間複雜度的演算法。測試範例
Example 1:
Input: nums = [2,2,3,2]
Output: 3
3是烙單的數字，只出現一次。
Example 2:
Input: nums = [0,1,0,1,0,1,99]
Output: 99
99是烙單的數字，只出現一次。
約束條件
Constraints:
1 <= nums.length <= 3 * 10^4
輸入陣列的長度介於1~三萬之間。
-2^31 <= nums[i] <= 2^31 - 1
每個陣列元素都在4byte整數範圍內。
- Each element in
numsappears exactly three times except for one element which appears once.
只有恰好一個數字烙單，其他剩餘的數字都剛好出現三次。
觀察
如果最直覺的想法，就是用字典去記錄每個數字的出現次數。
找出出現次數只有一次的數字即可。
演算法 二進位操作 + 狀態機
但是，困難點在於題目多了額外拘束，限定使用O(1)常數空間。
可以怎麼做呢?
教學影片
可以用State machine維持一個有限狀態機，分別記錄出現零次(等價於 mod 3 餘零)、一次、兩次的數字，並且用布林代數推導狀態更新公式。
其他的數字都會回到 mod 3餘零的狀態，只有落單的數字會停留在出現一次的狀態。
最後，留在出現一次的那個數字就是最終答案，也就是落單的數字。
程式碼 二進位操作+ 狀態機
class Solution:
def singleNumber(self, nums: List[int]) -> int:
state_one = 0
state_two = 0
for num in nums:
state_one = (num ^ state_one) & ~state_two
state_two = (num ^ state_two) & ~state_one
return state_one
複雜度分析
時間複雜度:O(n)
從左到右，掃描每個數字，每個數字計算一次。
空間複雜度: O(1)
使用到的都是固定尺寸的臨時變數，為常數級別O(1)。
關鍵知識點
這個系列題考點在於二進位操作、XOR運算子特性、布林代數的化簡。
強烈讀者建議一起複習。
二進位操作 尋找落單的數字 Single Number Leetcode #136 精選75題
萬綠叢中一點紅 落單的數字 Single Number III_二進位操作_Leetcode #260
