Problem: 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?

Solution: Single Number, Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Date : 2015-01-01 22:37:45
# @Author : NSSimacer
# @Version : 1.0
class Solution:
# @param A, a list of integer
# @return an integer
def singleNumber(self, A):
return 2 * sum(set(A)) - sum(A)

其他方法,可以采用异或位操作来实现

1
2
return reduce(operator.xor, A)