136.找出給定列表中落單的整數
Question:
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Example:
Input: [2,2,1]
Output: 1
果然是屬于 easy 的題目簿透。很簡單嘛椎木。2秒鐘后踪区。。径密。
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in nums:
if nums.index(i) + nums[::-1].index(i) == len(nums)-1:
return i
在線測試 finished 只用了三行代碼就搞定了，可把我牛逼壞了，哈哈
果斷提交WTF... 失敗了，提示：Time Limit Exceeded 怎么回事毯欣，原來是代碼運行時間太長不符合leetcode檢測要求。繼續(xù)看題目要求：
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
要求：您的算法應該具有線性運行時復雜度O(n)
嗯什么是時間復雜度O(n)與O(1)臭脓。大學也曾知道過，可惜都還給書本了腹忽，哎来累，百度一下 --- 授人以魚不如授人以漁，給你一本數據結構的書就懂了 ---mdzz
正確的姿勢如下：
引用一位大佬的解釋：
舉個簡單的例子窘奏，要從0加到n嘹锁，我們會這么寫：
int sum = 0;
for(int i = 0; i<=n; ++i)
{
sum += i;
}
一共算了n次加法，那么就說這個時間復雜度是O(n)着裹。當然O(n)的精確的概念是领猾，是n的最高次方，比如，某個計算共計算了3n + 2次摔竿，那么這個時間復雜度也是O(n)面粮，因為3n + 2中的最高次方是n。
如果代碼這么寫：
int sum = 0;
for(int i = 0; i<=n; ++i)
{
for(int j = 0; j <=n; ++j)
{
sum += (i + j);
}
}
很顯然一共算了n^2次加法继低，那么就說這個時間復雜度是O(n^2)熬苍，和上面類似，如果某個算法計算了3*n^2 + n + 1次袁翁，其時間復雜度仍然是O(n^2)柴底，因為3*n^2 + n + 1中最高的次方是n^2
所謂O(1)就是計算的次數是個常量，我們還以上面從0加到n的例子來說粱胜，如果我們用等差數列的公式柄驻，那么，代碼可以這么寫：
int sum = n * (n + 1) / 2
不管n有多大(當然不能溢出了)焙压，通過上面的公式只需計算一次鸿脓，也就說計算的次數是不變的，這種情況的時間復雜度就可以說成O(1)冗恨。 再比如如果某個計算答憔，不管其他條件怎么變化，均只需計算5次即可得出結果掀抹，那么這種情況的時間復雜度虐拓，也是O(1)。
怎么樣懂了吧傲武，本來還想試圖分析下蓉驹，還是算了。上面已經解釋的夠清晰了揪利，不添亂了态兴。果然 leetcode 還是有貨的，不能只學代碼疟位，否則就真成碼農了瞻润，反思下~~~
現在知道了自己的錯誤在哪里。繼續(xù)重新編輯：
class Solution:
def singleNumber(self, nums):
#52ms
nums.sort()
num = 0
j = 0
for i in nums:
if j%2 == 0:
num += i
else:
num += -i
j += 1
return num
#48ms
nums.sort()
for i in range(len(nums)//2):
if nums[-1] != nums[-2]:
return nums[-1]
nums.pop()
nums.pop()
return nums[0]
使用了倆種方式第一種52ms 第二種48ms 代碼很簡單甜刻，不需要解釋吧绍撞。其中nums.sort()的時間復雜度應該也是O(n)具體算法，以后有機會在分析得院，所函數總的時間復雜度也是O(n)符合要求傻铣。
1: nums.sort([reverse=True]) 會將nums列表正序排序，參數reverse=True 時會逆序排序
2: sorted(nums) 會返回一個新的序列祥绞。該函數可用于任何可迭代對象非洲，也存在reverse參數
來感受下官方給出的解決方案：Solution
前倆種方法不做分析鸭限，主要看一下。方法3和4两踏， 來感受一下數學的魅力
數學計算： 2?(a+b+c)?(a+a+b+b+c)=c
class Solution(object):
def singleNumber(self, nums):
return 2 * sum(set(nums)) - sum(nums)
位運算：
a⊕0=aa⊕a=0a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
⊕ 表示異或運算(按位相異為1 相同為0) XOR 舉個栗子：
2 0000 0010
0 0000 0000
2 xor 0 = 0000 0010 = 2
3 0000 0101
3 0000 0101
3 xor 3 = 0000 0000 = 0
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b 交換律請自行驗證
另外在python中有如下語法：
+, -, *, /, //, **, ~, %分別表示加法或者取正败京、減法或者取負、乘法缆瓣、除法喧枷、整除、乘方弓坞、取補隧甚、取模。>>, <<表示右移和左移渡冻。&, |, ^表示二進制的AND, OR, XOR運算戚扳。>, <, ==, !=, <=, >=用于比較兩個表達式的值，分別表示大于族吻、小于帽借、等于、不等于超歌、小于等于砍艾、大于等于。在這些運算符里面巍举，~, |, ^, &, <<, >>必須應用于整數脆荷。 Python使用and, or, not表示邏輯運算。
class Solution(object):
def singleNumber(self, nums):
a = 0
for i in nums:
a ^= i
return a
因為有a⊕b⊕a=(a⊕a)⊕b=0⊕b=b交換律存在懊悯，對所有數進行異或運算其中相同的2個數最終得到0蜓谋，最后運算結果為落單的數。
果然這才是程序猿該有的姿勢炭分，linux中一切皆文件桃焕。python中一切皆對象。但終究一切皆數學啊~~
接下來再嘗試下Single Number的升級版：
137.Single Numver II 也是找落單的數
question:
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
example:
Input: [2,2,3,2]
Output: 3
有了上面的基礎捧毛，這道題還是挺簡單的观堂。數學解法：3（a+b+c）-(3a+3b+c) = 2c
class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return (3*sum(set(nums)) - sum(nums))//2
完美通過。官方沒有給出標準的解決方案呀忧，本來還是想看看類似bit操作的解法型将，無奈搜了一下感覺很難，先這樣荐虐，我還有其他事要做，不能浪費在這丸凭。此處貼上解法的鏈接福扬，如果朋友們有興趣請自行研究腕铸，再來看看變種3
260.Single Numver III 找多個出現一次的數
question:
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
example:
Input: [1,2,1,3,2,5]
Output: [3,5]
仔細想了一番。暫時不能通過數學方法來得出結論铛碑。就用傳統(tǒng)的方法吧狠裹。而且該方法也比較通用，不論是針對整數的列表,還是針對字符串的列表都可以使用汽烦，大家可以使用該方法涛菠，以此將上面的題目實現一邊
class Solution:
def singleNumber(self, nums):
res_dir = {}
for i in nums:
if i not in res_dir:
res_dir[i] = 1
else:
del res_dir[i]
res = []
for key in res_dir:
res.append(key)
return res
很簡單的方法，一看代碼就清楚了撇吞。我想該題也有類似bit運算的解法俗冻。如有同學知道。還請賜教~~謝謝牍颈，Single Number 系列就先到這里
總結：
- 關于時間復雜度 O(n) 的定義
- 關于python中的一些位運算符
- 關于異或運算的規(guī)律
- 關于這種題的通用解法
- 巧用數學方法解題
聲明：
本人也是python 小白迄薄，如果上述內容有講的不對的地方還請各位批評指點。將不勝感激煮岁，再次感謝~~~
