力扣136.只出现一次的数字-异或和HashMap-编程实验室

问题描述

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

方法一：传统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)
代码简洁度	一般	简洁	极简
通用性	高（可处理任意次数）	高（可处理任意次数）	低（只适用于两次）
思维难度	低	中	高