题目描述：

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?

题目大意：

给定一个整数数组，除一个元素只出现一次外，其余各元素均出现两次。找出那个只出现一次的元素。

注意：

你的算法应该满足线性时间复杂度。可以不使用额外的空间完成此题吗？

解题思路：

对数组元素执行异或运算，最终结果即为所求。

由于异或运算的性质，两个相同数字的亦或等于0，而任意数字与0的亦或都等于它本身。另外，异或运算满足交换律。

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

使用Python的内置reduce函数可以将代码缩减为一行。

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

或者使用lambda表达式：

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

 

本文链接：http://bookshadow.com/weblog/2015/07/31/leetcode-single-number/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码