leetcode:136
<b>Question</b>(leetcode:136): Given an array of integers, every element appearstwiceexcept for one. Find that single one.(给定一个整型数组,每一个元素出现两次,只有一个元素出现一次,找到这个元素)
import operator
class Solution:
def singleNumber(self,A):
return reduce(operator.xor,A)
if __name__ == '__main__':
print Solution().singleNumber([1,1,2,3,2,4,4])
- 其中我们导入了python的operator的库,这个库主要提供一些基本的函数操作,这个函数中主要使用xor函数(异或函数)
xor(a,b) -> same as a ^ b
- 我们用到了python的高阶函数-reduce
reduce把一个函数作用在一个序列[x1, x2, x3...]上，这个函数必须接收两个参数，reduce把结果继续和序列的下一个元素做累积计算，其效果就是：
reduce(f, [x1, x2, x3, x4]) = f(f(f(x1, x2), x3), x4)
reduce(operato.xor,A) 等于下面
(( (1 ^ 1) ^ 2) ^ 3).....
- 核心是
((a ^ b) ^ a) = b
leetcode:137
<b>Question</b>: Given an array of integers, every element appears three times except for one. Find that single one.(给定一个数组,每一个元素出现3次,除了一个找到这一个)
class Solution3:
def singleNumber(self,A ):
one,two,three = 0,0,0
for x in A:
#是否是第二次相同
two = one & x | two
one = one ^ x
three = one & two
one = one & ~three
two = two & ~three
print 'one:%x,two:%x,three:%x' % (one,two,three)
if __name__ == '__main__':
print Solution3().singleNumber([4,4,3,4,1,1,1,2,3,3])
