Leetcode Algorithm-136. 只出现一次的数字

闲来无事刷题玩，顺带记录一下解题思路，方便未来二刷的时候来找思路。

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

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

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

直接map去处理，这一类的都归结为使用一个集合去过滤。

public int singleNumber(int[] nums) {
    Map map=new HashMap<>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    for (Map.Entry entry : map.entrySet()) {
        if (entry.getValue()==1){
            return entry.getKey();
        }
    }
    return 0;
}

异或运算有以下三个性质：
	1.任何数和 00 做异或运算，结果仍然是原来的数，即a^0=a或者0^a=a。
	2.任何数和其自身做异或运算，结果是0，即 a^a=0。
	3.异或运算满足交换律和结合律，即 a^b^a = b^a^a = b^(a^a)= b^0 = b。
因此当整个数组中的元素互相进行异或操作的时候，最后剩下的数字必然就是唯一的那个元素

public int singleNumber2(int[] nums) {
    int result=0;
    for (int n:nums) {
        result^=n;
    }
    return result;
}