## 题目描述：

Given an array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

## 解题思路：

`a ^ b = (a & !b) || (!a & b)`

## Python代码：

``````class Solution:
# @param {integer[]} nums
# @return {integer}
def singleNumber(self, nums):
ans = 0
for num in nums:
ans ^= num
return ans
``````

``````class Solution:
# @param {integer[]} nums
# @return {integer}
def singleNumber(self, nums):
return reduce(operator.xor, nums)
``````

``````class Solution:
# @param {integer[]} nums
# @return {integer}
def singleNumber(self, nums):
return reduce(lambda x, y : x ^ y, nums)
``````

Python的reduce函数原型为：`reduce(function, iterable[, initializer])`

reduce函数从左向右依次对传入的iterable参数（例如list）套用函数执行“缩减”操作，例如reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) 的运算结果为： ((((1+2)+3)+4)+5)

reduce函数的实现可以粗略地表示为下面的Python代码：

``````def reduce(function, iterable, initializer=None):
it = iter(iterable)
if initializer is None:
try:
initializer = next(it)
except StopIteration:
raise TypeError('reduce() of empty sequence with no initial value')
accum_value = initializer
for x in it:
accum_value = function(accum_value, x)
return accum_value
``````

Pingbacks已关闭。