題目描述
給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)了三次。找出那個(gè)只出現(xiàn)了一次的元素。
說明：
你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？
示例 1:
輸入: [2,2,3,2]
輸出: 3
示例 2:
輸入: [0,1,0,1,0,1,99]
輸出: 99
解法
因?yàn)轭}目限定了數(shù)組中除了一個(gè)元素出現(xiàn)一次外，其他元素均出現(xiàn)三次。因?yàn)槟壳安]有三目運(yùn)算符，所以可以利用現(xiàn)有的邏輯運(yùn)算，來模擬三進(jìn)制的不進(jìn)位加法，對數(shù)組中每個(gè)元素進(jìn)行加法運(yùn)算，最后的結(jié)果就是只出現(xiàn)一次的元素。
參考二進(jìn)制的不進(jìn)位加法，即異或運(yùn)算:
xor(1,1)=0
xor(1,0)=1
xor(0,0)=0
三進(jìn)制的不進(jìn)位加法中，有一點(diǎn)不同的是，xor(1,1)的結(jié)果應(yīng)該存儲起來，再遇到相同位置的1時(shí)，即累加到3時(shí)，不進(jìn)位為0。類似于以下效果:
tor(1,1)=2
tor(2,1)=0
其中tor表示為三進(jìn)制的不進(jìn)位加法。
因?yàn)槎M(jìn)制位只能存儲01，所以這里需要借助兩個(gè)變量來存儲一個(gè)三進(jìn)制不進(jìn)位加法的結(jié)果。ones表示二進(jìn)制加法的結(jié)果，twos表示二進(jìn)制加法的進(jìn)位。如下所示：
tor(1,1)=(ones=0,twos=1)
tor(1,0)=(ones=1,twos=0)
tor(0,0)=(ones=0,twos=0)
計(jì)算規(guī)則：觀察可以發(fā)現(xiàn)，ones的值等同于二進(jìn)制的xor運(yùn)算結(jié)果，twos用來存儲1+1產(chǎn)生的進(jìn)位，即等同于&與運(yùn)算的結(jié)果。
所以以下代碼示例中，使用ones存儲二進(jìn)制加法的結(jié)果，twos存儲二進(jìn)制加法的進(jìn)位。
則對于元素num，根據(jù)計(jì)算規(guī)則，ones^num表示此次的二進(jìn)制加法結(jié)果，不妨以half_ones=ones^num表示該值，若half_ones與twos對應(yīng)位上的值都為1，則產(chǎn)生進(jì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。
由三進(jìn)制的不進(jìn)位加法規(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后，不進(jìn)位置0的情況。
根據(jù)計(jì)算規(guī)則，新增的進(jìn)位為ones&num，更新twos的結(jié)果為新增進(jìn)位和原有進(jìn)位置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
