YCBlogs 数组题精讲：数组中只出现一次的数字——HashMap、HashSet 与异或运算的三种解法

• 教程
• 技术博客
• 文档

本篇基于 YCBlogs 仓库 leetcode/01.数组/08.数组中只出现一次的数字.md 展开，针对经典面试题“找出数组中只出现一次的数字”给出完整解题路径：从 HashMap 计数、HashSet 增删到异或位运算三种方案的完整 Java 实现、复杂度对比与原理推导。读完后你将掌握“出现偶数次的元素互相抵消”这一位运算思想，并能将其迁移到更复杂的变体问题上。

一、题目要求

原文档给出的问题描述如下：

• 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
• 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

题目的关键约束有两点：

1. 数组非空，且唯一“落单”的元素只有一个，其余元素恰好出现两次；
2. 算法要求线性时间复杂度 O(n)，并进一步追问能否做到不使用额外空间 O(1)。

这两个追问实际上决定了三种解法的分层：第一种方案满足线性时间但空间为 O(n)；第二种方案同样 O(n) 空间但实现更简洁；第三种异或方案才真正回答“能否 O(1) 空间”——能。

二、问题分析：用示例理解题意

原文档给出两个示例：

示例 1：

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

示例 2：

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

以示例 2 为例，元素 1 出现两次、2 出现两次、4 只出现一次，因此答案是 4。这个“成对出现 + 唯一落单”的数据特征是所有解法的基础：只要有一种机制能让“出现两次的元素互相抵消、最后只剩落单者”，问题就迎刃而解。HashMap 靠“计数到 2 即淘汰”实现，HashSet 靠“二次出现即移除”实现，异或则靠位运算的x ^ x = 0天然实现。

三、方案一：HashMap 计数法

原文档的第一个思路：把所有值作为 Map 的 key，出现次数作为 value，最后次数为 1 的就是那个单个值。代码完整继承自原文档：

/** * 我能想到的第一个方法就是把所有的值当成 Map 的key，出现的次数当成value * 最后次数为 1 的就是那个单个的 */ @RequiresApi(api = Build.VERSION_CODES.N) public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (!map.containsKey(num)) { map.put(num, 1); } else { map.put(num, map.get(num) + 1); } } return map.entrySet().stream().filter(r -> r.getValue() == 1).findFirst().get().getKey(); }

逐段解析：

• 第一层循环做频率统计：遍历数组，元素首次出现时put(num, 1)，再次出现时自增为 2。遍历结束后，只有落单元素的计数停留在 1，其余全部为 2。
• stream 过滤取结果：filter(r -> r.getValue() == 1)筛出计数为 1 的键值对。findFirst().get()能安全取值，是因为题目保证了唯一解一定存在。
• @RequiresApi(api = Build.VERSION_CODES.N)注解的含义：原文档运行在 Android 工程中，map.entrySet().stream()这条集合 Stream API 需要 API 24（Android N）才可用，因此在 Android 低版本环境下需要该注解声明；如果放在纯 Java 8+ 桌面工程中，则无需此注解，可直接使用 stream。

复杂度分析（结合仓库 leetcode/00.导向/03.时间复杂度.md 中“只关注循环执行次数最多的一段代码”的方法）：

• 时间复杂度 O(n)：统计循环执行 n 次，stream 过滤最坏再遍历一次 map 的 n 个键值对，量级仍为 O(n)，符合题目“线性时间”要求；
• 空间复杂度 O(n)：最坏情况下所有元素互不相同前缀阶段，map 需要保存接近 n 个键值对，无法满足“不使用额外空间”的追问。

这是“计数问题”的通用第一反应，正确但非最优，适合作为思维起点。

四、方案二：HashSet 增删法（加一遍、删一遍）

原文档的第二个思路：看到重复元素，本能地想到 Set——把出现两次的数字先添加到 Set 里面，然后再移除掉，最后剩下的就是单个的值。完整代码：

/** * 看到重复元素，本能的想到 Set,可以考虑把出现两次的数字先添加到 Set 里面，然后再移除掉， * 最后剩下一个就是单个的值。 */ public int singleNumber1(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) { if (!set.remove(num)) { set.add(num); } } return set.iterator().next(); }

这段代码的精髓在if (!set.remove(num))这一行：

• HashSet.remove(e)返回boolean：移除成功返回 true，元素本就不存在返回 false；
• 因此逻辑是：先尝试删除，删掉了（说明这是第二次出现）什么都不做；没删掉（说明这是第一次出现）就加入集合；
• 遍历结束后，Set 里只剩落单元素，iterator().next()直接取出。

相比 HashMap 方案，HashSet 方案有两个优点：一是无需显式维护计数（Set 的存在性天然等价于“出现奇数次”），二是空间上只存元素本身而非键值对，常数更小。但其时间复杂度仍为 O(n)、空间复杂度仍为 O(n)（见 leetcode/00.导向/04.空间复杂度.md 中“空间复杂度表示算法存储空间与数据规模的增长关系”的定义，此处随 n 线性增长的正是 Set 本身）。

理解 Set 方案的机制时，可延伸阅读仓库中 leetcode/08.Hash/08.Java中Hash应用.md 关于散列函数、hash 冲突与链地址法的内容——HashSet底层依赖HashMap，其增删查的均摊 O(1) 表现正是建立在哈希表这一结构之上。

五、方案三：异或位运算法（最优解，O(1) 空间）

原文档的第三个思路是本题的正解，也是唯一满足“线性时间 + 无额外空间”的方案：

/** * 异或(^) 运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1） * 除了其中一个数字是一次外，其他的都是两次，相同的值异或结果为0，用0异或所有的值， * 最终结果就是那个单个的值。 */ public int singleNumber2(int[] nums) { int r = 0; for (int num : nums) { r ^= num; } return r; }

5.1 异或运算的三条关键性质

异或（XOR，^）是逐位进行的按位运算，0⊕0=0、1⊕0=1、0⊕1=1、1⊕1=0，即“同 0 异 1”。由此可推出三条对本题至关重要的性质：

1. 交换律与结合律：a ^ b ^ c与运算顺序无关，因此无论数组元素以什么顺序出现，累加异或的结果都一样；
2. 自反性x ^ x = 0：任何数异或自身为 0，这正是“出现两次的元素互相抵消”的数学保证；
3. 单位元x ^ 0 = x：0 是异或的单位元，因此可以令累加器初始值为 0，逐位“吸收”数组元素而不改变最终结果。

5.2 以 [4,1,2,1,2] 逐步模拟

按r ^= num顺序执行：

最终 r = 4，与题目示例 2 的输出一致。注意第 2 步与第 4 步：元素 1 第一次进入累加器（0101），第二次出现时7 ^ 1 = 6又把它“消掉”了（0110），两个 1 的贡献恰好归零。用 [2,2,1] 同样验证：0^2=2 → 2^2=0 → 0^1=1，结果为 1。

5.3 为什么“抵消”总是成立

成对出现的每个元素 x 会贡献两次^ x，根据结合律可将其相邻看待：... ^ x ^ x ^ ... = ... ^ (x ^ x) ^ ... = ... ^ 0 ^ ...，即该元素对最终结果毫无影响；剩下的唯一元素 y 只贡献一次，最终0 ^ y = y。因此无论落单元素在数组什么位置，结果都等于它本身。

复杂度：单次遍历，每个元素只做一次异或操作，时间复杂度 O(n)；除累加器r外不申请任何与 n 相关的存储，空间复杂度 O(1)，完美回答了题目的追问。

六、三种方案对比小结

选型建议：面试先给出异或解法点明最优复杂度，再说明 Hash 方案作为“允许 O(n) 空间时的通用兜底”；工程上若题设放宽为“其余元素出现 k 次（k 为奇数次以外的任意值）”，HashMap 计数法仍是更稳妥的通用手段。

七、进阶延伸：两个只出现一次的数字

仓库中紧接的 leetcode/01.数组/21.数组中只出现一次的数字.md 给出了本题的经典变体：

• 一个整型数组里除了两个数字之外，其他数字都出现了两次，要求 O(n) 时间、O(1) 空间找出这两个数字；
• 示例：输入{2, 4, 3, 6, 3, 2, 5}，输出 4 和 6。

其解法正是建立在本文异或思想之上的递进：先把整个数组异或，得到a ^ b（两个落单者的异或结果，成对元素全部抵消）；由于a ≠ b，该结果二进制中必有 1 位，取其第一个为 1 的位作为分组标准，把数组拆成两组——出现了两次的相同数字任意对应位相同，必然被分进同一组，于是每组都退化为“唯一单数”问题，再各做一次异或即可。原文档中的实现（findFirstBit1用无符号右移>>>逐位探测、isBit1判断分组位）完整保留了这一分组-再异或的两阶段流程，值得对照本文方案三一起研读，以掌握“异或抵消”思想从一题到变体的迁移方法。

八、仓库内相关阅读

• leetcode/01.数组/08.数组中只出现一次的数字.md：本文主体来源，三种解法原始代码；
• leetcode/01.数组/21.数组中只出现一次的数字.md：两个落单数字的分组异或进阶解；
• leetcode/00.导向/03.时间复杂度.md 与 leetcode/00.导向/04.空间复杂度.md：复杂度分析方法的基础铺垫；
• leetcode/08.Hash/08.Java中Hash应用.md：HashMap/HashSet 底层散列机制的背景知识。

• 教程
• 技术博客
• 文档