本文概览：本文讲解只出现一次的数字：其余数字都出现两次，异或运算满足 a^a=0、a^0=a 且可交换可结合，把所有数字全异或一遍，成对的互相抵消成 0，剩下的就是答案。用二进制逐位演示抵消过程，O(n) 时间、O(1) 空间

一、题目

image-20260926100000001

二、题目分析

1. 题目要求

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

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

示例 1：nums = [2, 2, 1] → 1

示例 2：nums = [4, 1, 2, 1, 2] → 4

示例 3：nums = [1] → 1

2. 怎么想这题？

题目给出的条件里有个关键信息：除了答案，其他数字都是成对出现的。

那最直观的思路就来了——怎么把"成对"的数字消掉、只留下那个落单的？顺着这个想法，有几条路可以走：

  • 用哈希集合把出现过的数字记下来：第一次遇到就放进去，第二次遇到就说明它成对了，从集合里删掉。最后集合里剩下的就是那个落单的。这条路好想，但要多花 O(n) 的空间。
  • 排序之后两两比较，成对的会挨在一起，扫一遍就能找出落单的。这是 O(n log n)，也没达到"线性"的要求。
  • 有没有一种运算，天生就能让两个相同的数互相抵消？有，就是异或。它比前两条路都好，因为既快又不需要额外空间。

3. 需要解决哪几个问题？

问题一：哈希集合和排序这两条路，为什么达不到题目"线性 + 不用额外空间"的要求？

问题二（核心）：异或为什么能让相同的数字互相抵消？从二进制位上到底发生了什么？

问题三：为什么把所有数字一股脑异或起来（完全不管顺序）也能得出正确答案？

三、方法一：哈希集合，O(n) 空间

1. 思路概览

1
2
3
4
5
6
7
8
9
10
public int singleNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (!set.add(num)) {
            // add 返回 false 说明这个数已经在集合里了，是对里的第二个
            set.remove(num);
        }
    }
    return set.iterator().next();
}

思路简要说明：

  1. 进进出出：第一次遇到某个数就放进去，第二次遇到（add 返回 false）说明它成对了，从集合里移走
  2. 剩下的就是答案：所有成对的都被移走了，集合里只剩那个落单的
  3. **时间复杂度 O(n)**，空间 O(n)
  4. 不满足进阶要求：用了 O(n) 的额外空间

2. 思路详解

这个思路就是拿集合模拟"配对"的过程。set.add(num) 会返回一个布尔值：放进去之前集合里没有这个数就返回 true，已经有了就返回 false。所以：

  • 第一次遇到 4：集合里没有 → add 返回 true → 留着；
  • 第二次遇到 4：集合里已经有了 → add 返回 false → 说明这一对凑齐了，两个一起消掉（把 4 从集合里 remove）。

以 [4, 1, 2, 1, 2] 为例：

1
2
3
4
5
6
遇到 4：set = [4]
遇到 1：set = [4, 1]
遇到 2：set = [4, 1, 2]
遇到 1：1 已存在 → set = [4, 2]
遇到 2：2 已存在 → set = [4]
返回 4 ✓

逻辑很直白，代价是那个集合占用了 O(n) 的空间——题目偏偏要求"不使用额外空间"。

3. 复杂度分析

**时间复杂度 O(n)**：遍历一次，哈希操作均摊 O(1)。

**空间复杂度 O(n)**：最坏情况下集合里存近 n 个数。

四、方法二：排序后两两比较，O(n log n)

1. 思路概览

1
2
3
4
5
6
7
8
9
public int singleNumber(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i + 1 < nums.length; i += 2) {
        if (nums[i] != nums[i + 1]) {
            return nums[i];
        }
    }
    return nums[nums.length - 1];
}

思路简要说明：

  1. 排序让成对的数字挨在一起：排完之后相同的数一定相邻
  2. 两两跳着扫：每次看一对 (nums[i], nums[i+1])，不相等说明 nums[i] 就是落单的
  3. 扫完没找到：说明落单的是最后一个元素
  4. **时间复杂度 O(n log n)**，空间 O(1)（不算排序本身的开销）

2. 思路详解

排序会把相等的元素排到一起，所以数组变成"一对、一对……最后可能单一个"的样子。于是从下标 0 开始，每次跨两步看一对：

  • 如果这一对相等，说明这对配上了，往后跳两步继续；
  • 如果这一对不相等，说明前一个数没有同伴——它就是答案。

用 [4, 1, 2, 1, 2] 举例，排序后是 [1, 1, 2, 2, 4]：

1
2
3
i=0：nums[0]=1 和 nums[1]=1 相等 → 跳过
i=2：nums[2]=2 和 nums[3]=2 相等 → 跳过
i=4：i+1 越界，循环结束 → 返回最后一个 4 ✓

这个方法空间省了，但排序要 O(n log n)，比线性的要求慢一截。

3. 复杂度分析

**时间复杂度 O(n log n)**：排序占主要开销。

**空间复杂度 O(1)**：只用了下标变量。

五、方法三：异或，O(n) 时间 + O(1) 空间

1. 思路概览

1
2
3
4
5
6
7
public int singleNumber(int[] nums) {
    int ans = 0;
    for (int num : nums) {
        ans ^= num;
    }
    return ans;
}

思路简要说明：

  1. 一个变量一路异或到底：ans 从 0 开始，把每个数都异或进去
  2. 成对的自动抵消：两个相同的数异或得 0，等于没参与
  3. 剩下的就是答案：所有成对数字抵消完，ans 里留下的只有那个落单的
  4. **时间复杂度 O(n)**，空间 O(1)

2. 思路详解

第一步：解决"为什么异或能抵消"——先看异或在二进制位上的规则

异或（^）是按位运算：先把两个数都写成二进制，再让它们一位对齐一位地算。因为是二进制，每一位上只可能是 0 或 1 两种值，两个位碰在一起一共也只有四种组合，规则就两条：

1
2
相同得 0：0 ^ 0 = 0     1 ^ 1 = 0
不同得 1：0 ^ 1 = 1     1 ^ 0 = 1

这里要特别注意，上面式子里的 0 和 1 全都是二进制位（bit）上的值，说的是"这一位取 0 还是取 1"，不是十进制的数字 0 和 1。所以这四行的意思是：把某一位上的两个 bit 做异或，得到的结果 bit 是 0 还是 1——两个 bit 相同，结果 bit 就是 0；两个 bit 不同，结果 bit 就是 1。

一句话记住："相同得 0，不同得 1"。

由此立刻能推出两个性质：

1
2
a ^ a = 0     ← 两个一模一样的数，每一位上的两个 bit 都相同，逐位算出来都是 bit 0；一位一位全是 0，整个数就是 0
a ^ 0 = a     ← 每一位拿 bit 和 0 去比：原来是 bit 1 的"不同得 1"，原来是 bit 0 的"相同得 0"，结果原样不动

第一个性质正是我们想要的：两个相同的数异或，结果就是 0，等于互相抵消没出现过。

第二步：把示例 2 拆成二进制看抵消过程

拿 nums = [4, 1, 2, 1, 2] 来，先把每个数写成二进制：

1
2
3
4
5
4 = 1 0 0
1 = 0 0 1
2 = 0 1 0
1 = 0 0 1
2 = 0 1 0

现在一位一列地竖着看，每一位各自做异或：

1
2
3
4
5
6
7
8
        位2   位1   位0
  4      1     0     0
  1      0     0     1
  2      0     1     0
  1      0     0     1
  2      0     1     0
------------------------
结果     1     0     0   = 4

逐位解释：

  • 位 0：这一列是 0、1、0、1、0。两个 1 来自那两个 1，异或时 1 ^ 1 = 0，正好抵消，最后剩 0。
  • 位 1：这一列是 0、0、1、0、1。两个 1 来自那两个 2，同样抵消，剩 0。
  • 位 2：这一列是 1、0、0、0、0。只有 4 贡献了一个 1，没有谁能和它抵消，于是留下 1。

三位合起来 1 0 0，正是 4——那个落单的数。

换一个角度：把整个异或过程一步步算出来

1
2
3
4
5
6
ans 初始     = 000
ans ^ 4      = 000 ^ 100 = 100   → 4
ans ^ 1      = 100 ^ 001 = 101   → 5
ans ^ 2      = 101 ^ 010 = 111   → 7
ans ^ 1      = 111 ^ 001 = 110   → 6
ans ^ 2      = 110 ^ 010 = 100   → 4 ✓

中间几步的 ans 是 5、7、6，看着毫无规律，但那只是"还没配上对"的临时状态。等到把 1 和 1、2 和 2 都异或进去，它们两两抵消，最后只剩 4。

这也说明一件事：不需要关心中间过程是什么，只要保证每个数字都被异或了一次，成对的就会自己消掉。

第三步：解决"为什么可以不管顺序"

异或满足交换律（a ^ b = b ^ a）和结合律（(a ^ b) ^ c = a ^ (b ^ c)）。

原因从"按位独立"就能看出来：异或的每一位各算各的，不同位之间互不影响。而单独看某一位，这一位上无非是一堆 0 和 1，1 的个数是偶数就全抵消、是奇数就留一个 1——数一数就行，跟谁先谁后毫无关系。

所以整个数组可以看成"所有数字一起异或"，怎么打乱顺序、怎么分组都行：

1
2
3
4
4 ^ 1 ^ 2 ^ 1 ^ 2
= (1 ^ 1) ^ (2 ^ 2) ^ 4      ← 用交换律结合律把成对的挪到一起
= 0 ^ 0 ^ 4
= 4

成对的都变成了 0，0 ^ 4 = 4（a ^ 0 = a），答案就浮出来了。

第四步：代码细节

1
2
3
4
5
int ans = 0;      // 从 0 开始，因为 0 异或任何数都是那个数本身（0 ^ x = x）
for (int num : nums) {
    ans ^= num;   // 逐个异或进去
}
return ans;
  • 为什么初值是 0：0 ^ x = x，0 是异或运算的"零元"，拿它起步不会影响结果。
  • 数组只有一个元素：循环走一遍，ans = 0 ^ nums[0] = nums[0]，直接返回它自己，符合预期。
  • 负数也没问题：异或是补码上按位算的，性质 a ^ a = 0、a ^ 0 = a 对负数一样成立。

3. 复杂度分析

**时间复杂度 O(n)**：一次遍历，每个数只做一次异或。

**空间复杂度 O(1)**：只用一个变量 ans。

六、总结

方法 时间 空间 是否满足进阶要求
哈希集合 O(n) O(n) 否
排序 + 两两比较 O(n log n) O(1) 否（时间不够线性）
异或 O(n) O(1) 是

这题的关键在于抓住"其余元素都出现两次"这个条件，然后找到一种"相同的两个数碰一起就消失"的运算——异或正好就是：

  • a ^ a = 0：成对的自动抵消；
  • a ^ 0 = a：落单的不受影响；
  • 可交换、可结合：所以能无视顺序，从头到尾一把梭。

前两种方法都能算出答案，但一个要多花空间、一个要多花时间；异或同时把时间和空间都做到了最优，而且代码只有三行。