136.只出现一次的数字

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

说明：

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

示例 1:

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

数组中的元素出现次数，有特殊出现次数的数字

Solution：位运算

考虑异或运算，相同为0，相异为1

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;//除了single以外的其他数，出现了两次，所以异或为0，而single和0异或，结果为
    }
}

Solution2:Hash表

位运算只能说是取巧解法，假设其他数字出现两次以上，那么异或运算就不成立了，所以关于数组里面的元素出现次数的通用解法应该是HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) {
            int count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        for(Integer i:map.keySet()){
           Integer ans=map.get(i);
           if(ans==1){
               return i;
           }
        }
        return -1;
    }