# 136. 只出现一次的数字

# 题目描述

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

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

示例 1：

输入：nums = [2,2,1]
输出：1

1
2

示例 2：

输入：nums = [4,1,2,1,2]
输出：4

1
2

示例 3：

输入：nums = [1]
输出：1

1
2

提示：

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
除了某个元素只出现一次以外,其余每个元素均出现两次。

# 思路

这道题如果不考虑空间限制,很容易想到用哈希表统计每个元素出现次数,然后找出现一次的元素。

但题目要求只使用常量额外空间,哈希表就不行了,空间复杂度是 O(n)。

那怎么办呢?这就需要用到位运算中的异或(XOR)了。

# 异或运算的性质

异或运算有几个重要性质:

任何数和 0 异或,结果是它本身: a ^ 0 = a
任何数和它本身异或,结果是 0: a ^ a = 0
异或满足交换律和结合律: a ^ b ^ a = a ^ a ^ b = 0 ^ b = b

第三条性质是关键!

如果我们把数组中所有元素都异或起来,出现两次的元素会相互抵消变成 0,最后剩下的就是只出现一次的元素。

例如 [4,1,2,1,2]:

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)  // 交换律和结合律
= 4 ^ 0 ^ 0
= 4

1
2
3
4

这就是本题的最优解法:一次遍历,所有元素异或,时间O(n),空间O(1)。

# 模拟过程

以 nums = [4,1,2,1,2] 为例:

初始状态:

result = 0

遍历过程:

当前元素	异或操作	result (二进制)	result (十进制)
4	0 ^ 4	0100	4
1	4 ^ 1	0101	5
2	5 ^ 2	0111	7
1	7 ^ 1	0110	6
2	6 ^ 2	0100	4

最终结果: 4

我们也可以按配对的方式理解:

4 ^ 1 ^ 2 ^ 1 ^ 2
= 4 ^ (1 ^ 1) ^ (2 ^ 2)
= 4 ^ 0 ^ 0
= 4

1
2
3
4

drawio 提示词: 画两张图说明异或抵消原理。第一张展示数组 [4,1,2,1,2],用相同颜色标注成对的元素(两个1用蓝色,两个2用绿色,4用红色单独标注),并在下方列出异或的三条性质。第二张展示异或的计算过程,用树状图或分组的形式表现 4 ^ (1^1) ^ (2^2) = 4 ^ 0 ^ 0 = 4 的化简过程,配对的元素用箭头指向 0。两张图画布统一,Logo 放左下角。

文件名:

0136.single-number-01-pairing.drawio
0136.single-number-02-xor-process.drawio

# 解题代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        
        for (int num : nums) {
            result ^= num; // 所有元素异或
        }
        
        return result; // 出现两次的抵消,剩下只出现一次的
    }
};

1
2
3
4
5
6
7
8
9
10
11
12

# 复杂度分析

时间复杂度:O(n),需要遍历一遍数组
空间复杂度:O(1),只用了一个变量

# 其他语言

# Python3

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        
        for num in nums:
            result ^= num
        
        return result

1
2
3
4
5
6
7
8

# Java

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        
        for (int num : nums) {
            result ^= num;
        }
        
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11

# Go

func singleNumber(nums []int) int {
    result := 0
    
    for _, num := range nums {
        result ^= num
    }
    
    return result
}

1
2
3
4
5
6
7
8
9

# JavaScript

var singleNumber = function(nums) {
    let result = 0;
    
    for (const num of nums) {
        result ^= num;
    }
    
    return result;
};