目录

1.题目2.思路与实现3.总结思路与实现4.相关知识

1.题目

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

说明：

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

示例 1:

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

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

2.思路与实现

哈希表：使用哈希表存储元素和出现的次数，遍历数组即可得到每个数字出现的次数，最后遍历哈希表得到结果 时间N 空间N

class Solution { public int singleNumber(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for(int num : nums) { if(map.containsKey(num)) map.put(num, 2); else map.put(num, 1); } for(Integer temp: map.keySet()) { if(map.get(temp) == 1) return temp; } return 0; } }

3.总结思路与实现

最快：位运算 异或运算的特点：异或自身为0，异或0 为原数，满足加法交换律和结合律

class Solution { public int singleNumber(int[] nums) { int res = 0; for(int i = 0; i < nums.length; i++) { res ^= nums[i]; } return res; } }

时间N 空间1

4.相关知识

遍历哈希表的四种方式

最推荐的方式：使用Map.Entry for(Map.Entry<Integer, Integer> entry : map.entrySet()) { entry.getKey(); entry.getValue(); } map.keySet()获得键的集合map.values()获得值的集合