給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。
說明：
你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現(xiàn)嗎？
示例 1:
輸入:[2,2,1]輸出:1
示例?2:
輸入:[4,1,2,1,2]輸出:4
觀察思考，認真讀題，給了一個數(shù)組，非空！其中一個元素只出現(xiàn)一次，其他元素都出現(xiàn)二次！返回那個只出現(xiàn)一次的數(shù)字！
要求線性時間復雜度，不使用額外空間。
重點應該在于其他元素都出現(xiàn)2次。那么數(shù)組長度應該是2n+x，必為奇數(shù)，
對列表中所有元素計數(shù)，為1返回，沒什么大問題，好使，但是超時了
現(xiàn)在有的條件是2N+X? ?，思維有點固化了，一直思考如何做減法，但是列表不能做減法，利用集合獲得N+X，有2N+X和N+X好似好求X，但是百度幾種代替減法的方法都會去除X，利用集合相減那就是N+X? ?-? N+X，for循環(huán)尋找公共元素得到N+X，對N計數(shù)的話不如直接計數(shù)手游元素找不是2的，但那樣也是超時了，并且這種方法占用大量的空間。應該更換思路了。
在家也不閑著，昨天同學找吃飯，今天上午忙點事，現(xiàn)在下午了，昨天出去吃飯前看了一下別人的答案，用到了? ^? ?，復習一下這個吧
直接截圖粘貼了，這些符號在python中都被稱作位運算符，
位操作是程序設(shè)計中對位模式按位或二進制數(shù)的一元和二元操作。
計算機只認識0和1，也就是二進制，而人類很難理解，于是就有了位運算符稱作0和1，如實現(xiàn)A+B不用加號運算，用的就是位運算符。
一個個講解
& 按位與運算??
當兩個開關(guān)都為真，及連接時才能亮燈，在python中，何時為false,何時為trun,一般為0，或為空時為false，如數(shù)字0，空集合，空列表，空字符串，空字典，空字符串，還有表示什么都不在的None。其他都為trun。
所以操作時0&0=0,表示連個開關(guān)都為關(guān)，燈也就不亮，0&1=1，表示一個開關(guān)斷開，一個開關(guān)連接，燈還是不亮，1&1=1，連個開關(guān)都連接，那么燈也亮。100&100=100.不為0，表示都連接，燈亮，100都可以認為是表示真。100&0=0，一個不連接就不亮
但5&6=4，為什么呢？重新看一下名字，按位與運算符。a&b，計算機只認識二進制數(shù)0和1，&符號運算規(guī)則是都為1就記作1，否則記作0.
先將5和6變成二進制數(shù)，內(nèi)置函數(shù)bin()將10進制轉(zhuǎn)換為2進制。
bin(5)=? ?1? ?0? ?1
bin(6)=? ?1? ?1? ?0
5&6? ?=? ?1? ?0? ?0
再將2進制轉(zhuǎn)換為10進制，內(nèi)置函數(shù)int? ? int('100',2)=4
第二個運算符是? |? ?鍵盤不好找，shift加反斜杠
|? ?或運算，一真及真，
我畫的好像是電阻，不是電池，無所謂了，如圖所示，只要有一個開關(guān)連通就行。
按位或運算時只要不是a|b都不為0就行，也就是但a|b=0,那就是a=b=0.
然后就是今天的關(guān)鍵了，^，按位異或運算符，
按位運算是對二進制數(shù)的，那就是不是0就是1，對于^,當對應的二進制位相異時為1。
如bin(22)=1? ?0? ?1? ?1? ?0
????bin(7)=? ? ? ? ? ? 1? ?1? ?1? ? ? ? ? ??
? ? ? ? ? ? ? = 1? ?0? ?0? ?0? ?1
對位相異為1，不對位直接落下，相同就為0
0^0=0
0^8=? ? 0? ?0? ?0? ?0
? ? ? ? ? ? 1? ?0? ?1? ?0?
? ? ? ? ? ? 1? ?0? ?1? ?0
0^x? 如果x不為零，那么0^x=x? ? 如果x=0,0^0=0，0也是0本身
任何數(shù)和0做異或操作都為其本身
? ? ?x^x =? *? *? *? *
? ? ? ? ? ? ? ?*? *? *? *
? ? ? ? ? ? ? ? 0 0 0 0? ? ? ? ? ?任何數(shù)與其本身做異或操作都等于0? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
理解這些剩下的就簡單了
~按位取反運算符
如bin(9)=1001
~9就是對1001按位取反，0變1,1變0，那就是0110
int('0110',2)=6
<<左移運算符
>>右移運算符
箭頭指向哪里就是什么移
4<<1? ?就是4的二進制數(shù)向左移動1位
bin(4)=? ? ? ?1? ?0? ?0
?4<<1=? 1? ?0? ?0? ?0? ? =? 8? ?左移用0填補末尾
8>>2? 就是8的二進制數(shù)向右移動兩位
bin(8) =? ? 1? ?0? ?0? ?0
8>>2? =? ? ? ? ? ? ? 1? ?0? ?=? 2? ?左移多余部分舍去
按位運算符復習完了
回歸題目，一個2N+X數(shù)組求X
res =0
for i in nums:
? ? res = res ^ i
return =? res
起始為0,與nums[i]進行異或操作，
即為nums[0]^nums[1]^nums[2]^nums[3]^nusm[4]……
2N+X即N與自身做異或操作結(jié)果為0,0與X做異或操作為X
再看另一個方法，耗時長，先創(chuàng)建一個空列表，遍歷nums,如果i不在新列表中，加入新列表，在里面，去除，什么情況會在里面，那就是已經(jīng)添加進去了，已知2N+X，N一定會添加一次，第二次想添加時發(fā)現(xiàn)已存在，用remove（i）的方法的去除，最終剩下X。
