题目

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

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

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

自解

这次直接自解都写不出了，不用空间完全想不到。

官方解法

对于这道题，可使用异或运算⊕。异或运算有以下三个性质。

1. 任何数和0做异或运算，结果仍然是原来的数，即a⊕0=a
2. 任何数和其自身做异或运算，结果是0，即 a⊕a=0
3. 异或运算满足交换律和结合律，即a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b

假设数组中有2m+1个数，令a1,a2...am为出现两次的m个数，an为出现一次的数。
根据性质3，数组中的全部元素的异或运算结果总是可以写成如下形式：

`(a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(am⊕am)⊕an` 根据性质 2 和性质 1，上式可化简和计算得到如下结果： `0⊕0⊕⋯⊕0⊕am+1`=`an` ### 代码

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

---

https://leetcode-cn.com/problems/single-number/solution/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-solution/