寻找落单数
题目 【寻找落单数】给一个整数数组，其中除了只有一个数只出现一次以外，其他每一个数都出现两次。找出这个数。
注意：能否不使用额外空间？
解法 思路1 集合
遍历数组，用一个集合保存出现过1次的元素，若出现第二次则删除，最后集合剩下的一个值即为所求。
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
l = set([])
for i in nums:
if i not in l:
l.add(i)
else:
l.discard(i)
return l.pop()
思路2 求差
2?(a+b+c)?(a+a+b+b+c)=c用代码表示即为
2 * sum(set(nums)) - sum(nums)思路3 异或 （原地算法）
所有数进行异或，即得所求
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a = 0
for i in nums:
a ^= i
return a
推荐阅读
- 赠己诗
- 如何寻找情感问答App的分析切入点
- 《失落的百年致富圣经》读后感
- 让眼泪滑落，成为骄傲(三十九)
- 堕落不需要理由，只需要借口
- 恶魔天使
- 字符串拼接成段落，换行符（\n）如何只执行n-1次
- 爱TA，就要好好吃了TA
- 苗栗三灣鄉落羽松
- 今日的喜欢