136. 只出现了一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例

输入: [2,2,1]
输出: 1

输入: [4,1,2,1,2]
输出: 4

思路解析

这道题的难度值为easy，感觉更像是智力题。如果没有对于空间限制的话，那这道题怎么做基本都可以，毕竟牺牲空间就可以换取时间。正是这里限制了空间利用，所以要稍微思考一下取一种巧妙的方法。

官方解答的思路很妙，巧用了异或运算。也就是说，相同的俩数会运算得到0，0和一个非零数异或得到该数字。所以只需要将数组中所有的数字一起异或运算，得到的值就是这一个单独的数字。

解法巧妙之余，python对于个算法的实现更是简洁，直接一行代码搞定。先上代码：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x ^ y, nums)

作为一个没见过稍微复杂函数的python小白需要记下以下两个函数的解释：

1. reduce() 函数会对参数序列中元素进行累积。它的第一个参数传一个函数，第二个参数传一个数据集合。通俗说，将该数据集合中的所有元素依次按照传入函数的方法运算得到一个最终结果。
2. lambda定义python中的匿名函数，相当于一个极简的函数，不用写return也会默认返回计算的值。

所以以上的两个函数，就将nums数组中de的所有元素进行以下运算：

((nums[0]⊕nums[1])⊕nums[2]…)⊕nums[n]

最终这个结果也就是单独的那个元素。代码非常简洁，赞👍