问题描述
给定一个非空整数数组，除了某个元素只出现一次外，其余每个元素都出现两次。找出那个只出现了一次的元素。
方法一：传统HashMap解法
思路分析
最直观的想法是：统计每个数字出现的次数，然后找出只出现一次的那个数字。
实现代码
class Solution { public int singleNumber(int[] nums) { // 创建HashMap来存储数字及其出现次数 Map<Integer, Integer> map = new HashMap<>(); // 遍历数组，统计每个数字出现的次数 for (int num : nums) { // 如果map中已经包含这个数字 if (map.containsKey(num)) { // 出现次数加1 map.put(num, map.get(num) + 1); } else { // 第一次出现，设为1 map.put(num, 1); } } // 遍历map，找到出现次数为1的数字 for (Integer key : map.keySet()) { if (map.get(key) == 1) { return key; } } // 理论上不会执行到这里（题目保证有解） return -1; } }复杂度分析
时间复杂度：O(n)，需要遍历数组一次，遍历map一次
空间复杂度：O(n)，最坏情况下需要存储n/2+1个键值对
优缺点
✅ 思路直观，容易理解
✅ 适用于更一般的情况（如找出出现奇数次/偶数次的数字）
❌ 需要额外的存储空间
❌ 代码相对冗长
方法二：HashMap改进版
思路分析
Java 8引入了一些新的API，可以让我们的代码更加简洁优雅。
实现代码
class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); // 使用getOrDefault简化代码 for (int num : nums) { // 如果num存在，获取当前值加1；如果不存在，用0加1 map.put(num, map.getOrDefault(num, 0) + 1); } // 使用entrySet同时获取key和value，避免多次查找 for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (entry.getValue() == 1) { return entry.getKey(); } } return -1; } }关键技术点
1. getOrDefault方法
getOrDefault方法在key存在时返回对应的value，不存在时返回指定的默认值（这里是0）。
2. entrySet遍历
// 使用entrySet（只需一次遍历） for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (entry.getValue() == 1) { // 直接获取value return entry.getKey(); // 直接获取key } }优缺点
✅ 代码更简洁
✅ 使用entrySet提升遍历效率
❌ 仍然需要额外的存储空间
方法三：异或运算的魔法
思路分析
这是一个需要点数学思维的解法，利用了异或运算的几个重要性质：
任何数和0异或等于它本身：a ⊕ 0 = a
任何数和自身异或等于0：a ⊕ a = 0
异或运算满足交换律和结合律：a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b
实现代码
class Solution { public int singleNumber(int[] nums) { int result = 0; for (int num : nums) { result ^= num; // 对每个数字进行异或运算 } return result; } }复杂度分析
时间复杂度：O(n)，只需遍历一次数组
空间复杂度：O(1)，只使用常数级别的额外空间
优缺点
✅ 时间复杂度最低
✅ 空间复杂度最优
✅ 代码极其简洁
❌ 需要理解异或运算的特性
❌ 仅适用于特定情况（其他数字都出现两次）
三种方法对比
| 特性 | 传统HashMap | 改进HashMap | 异或运算 |
|---|---|---|---|
| 时间复杂度 | O(n) | O(n) | O(n) |
| 空间复杂度 | O(n) | O(n) | O(1) |
| 代码简洁度 | 一般 | 简洁 | 极简 |
| 通用性 | 高（可处理任意次数） | 高（可处理任意次数） | 低（只适用于两次） |
| 思维难度 | 低 | 中 | 高 |
拓展思考
如果其他数字出现三次，只有一个出现一次？
这时候异或运算就不适用了，但可以使用HashMap或位运算的扩展解法。
如果有两个只出现一次的数字？
这需要更巧妙的位运算技巧，可以通过分组异或来解决。
总结
这道题目看似简单，却蕴含了丰富的算法思想：
HashMap解法：体现了最直接的"计数"思维，是解决频率统计问题的通用方法
API优化：展示了如何利用语言特性写出更优雅、高效的代码
异或解法：揭示了数学思维在算法中的强大威力
在实际开发中，我们通常选择HashMap解法，因为它通用且易于理解和维护。但在面试或竞赛中，异或解法往往更受青睐，因为它展示了候选人对问题的深入理解。
希望这篇文章能帮助你更好地理解不同的解题思路。记住，没有最好的算法，只有最适合场景的算法。
思考题：如果题目改为"除了一个数字出现一次外，其他数字都出现三次"，你能想到几种解法？
