題目描述
給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)了三次。找出那個只出現(xiàn)了一次的元素。
說明：
你的算法應(yīng)該具有線性時間復(fù)雜度。 你可以不使用額外空間來實現(xiàn)嗎？
示例 1:
輸入: [2,2,3,2]
輸出: 3
示例 2:
輸入: [0,1,0,1,0,1,99]
輸出: 99
解法
因為題目限定了數(shù)組中除了一個元素出現(xiàn)一次外，其他元素均出現(xiàn)三次。因為目前并沒有三目運算符，所以可以利用現(xiàn)有的邏輯運算，來模擬三進制的不進位加法，對數(shù)組中每個元素進行加法運算，最后的結(jié)果就是只出現(xiàn)一次的元素。
參考二進制的不進位加法，即異或運算:
xor(1,1)=0
xor(1,0)=1
xor(0,0)=0
三進制的不進位加法中，有一點不同的是，xor(1,1)的結(jié)果應(yīng)該存儲起來，再遇到相同位置的1時，即累加到3時，不進位為0。類似于以下效果:
tor(1,1)=2
tor(2,1)=0
其中tor表示為三進制的不進位加法。
因為二進制位只能存儲01，所以這里需要借助兩個變量來存儲一個三進制不進位加法的結(jié)果。ones表示二進制加法的結(jié)果，twos表示二進制加法的進位。如下所示：
tor(1,1)=(ones=0,twos=1)
tor(1,0)=(ones=1,twos=0)
tor(0,0)=(ones=0,twos=0)
計算規(guī)則：觀察可以發(fā)現(xiàn)，ones的值等同于二進制的xor運算結(jié)果，twos用來存儲1+1產(chǎn)生的進位，即等同于&與運算的結(jié)果。
所以以下代碼示例中，使用ones存儲二進制加法的結(jié)果，twos存儲二進制加法的進位。
則對于元素num，根據(jù)計算規(guī)則，ones^num表示此次的二進制加法結(jié)果，不妨以half_ones=ones^num表示該值，若half_ones與twos對應(yīng)位上的值都為1，則產(chǎn)生進位，如下所示:
h,t=o
1,1=0
1,0=1
0,1=0
0,0=0
左邊的h表示half_ones的位，中間的t表示twos的位，右側(cè)的o表示ones的值，ones的值依賴half_ones和twos的情況。觀察可發(fā)現(xiàn)ones=half_ones&~twos，即ones=ones^num&~twos。
由三進制的不進位加法規(guī)則可知，若twos與元素num的對應(yīng)位上的值都為1，則置twos與ones的對應(yīng)位為0。ones的值已經(jīng)經(jīng)過處理，此處觀察twos與num的對應(yīng)位關(guān)系，如下所示:
t,n=h
1,1=0
1,0=1
0,1=0
0,0=0
左邊的t表示twos的位，中間的n表示num的位，右側(cè)的h表示half_twos的值，half_twos的值依賴twos和num的情況。觀察可發(fā)現(xiàn)half_twos=twos&~num，此處的half_twos表示加num后，不進位置0的情況。
根據(jù)計算規(guī)則，新增的進位為ones&num，更新twos的結(jié)果為新增進位和原有進位置0的情況，即twos=(ones&num)|(twos&~num)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ones,twos=0,0
for num in nums:
ones,twos=ones^num&~twos,ones&num|(twos&~num)
return ones
