LeetCode HOT 100 —— 136.只出现一次的数字

题目

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

思路

方法一：Hash表

class Solution{
          
   
	public int singleNumber(int[] nums){
          
   
		Map<Integer, Integer> map = new HashMap<>();
		//加入每个数字，并记录出现次数
		for(Integer i : nums){
          
   //这里要用Integer，因为map.get()为空的话会返回null，如果是int类型默认空为0，无法接收，Integer默认空为null
			Integer count = map.get(i);
			count = (count == null ? 1 : ++count);
			map.put(i, count);
		}
		//寻找出现次数为1的那个数字
		for(Integer i : map.keySet()){
          
   //获取所有的key值
			Integer count = map.get(i);
			if(count == 1){
          
   //如果出现次数为1，那么就找到了这个出现一次的数字 
				return i;
			}
		}
		return -1;
	}
}

方法二：异或运算

1. 交换律：a ^ b ^ c <=> a ^ c ^ b
2. 任何数于 0 异或为任何数本身 ：0 ^ n => n
3. 相同的数异或为 0 : n ^ n => 0

比如：var a = [2,3,2,4,4]，2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3

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