LeetCode： Single Number 系列
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检测要求。继续看题目要求：
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 还是有货的，不能只学代码，否则就真成码农了，反思下~~~
现在知道了自己的错误在哪里。继续重新编辑：
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]
仔细想了一番。暂时不能通过数学方法来得出结论。就用传统的方法吧。而且该方法也比较通用，不论是针对整数的列表,还是针对字符串的列表都可以使用，大家可以使用该方法，以此将上面的题目实现一边
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中的一些位运算符
- 关于异或运算的规律
- 关于这种题的通用解法
- 巧用数学方法解题
声明：
本人也是python 小白，如果上述内容有讲的不对的地方还请各位批评指点。将不胜感激，再次感谢~~~
