Leetcode No.只出现一次的数字

题目大意

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例1：

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

示例2：

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

方法一:排序

最开始的想法是将数组排序，然后一次遍历可找出只出现一次的数。使用快排的时间复杂度为O（nlogn）。

public int singleNumber(int[] nums) {
           if(nums.length==1) return nums[0];
        Arrays.sort(nums);
        for(int i=0;i<nums.length-1;i+=2)
           if(nums[i]!=nums[i+1]) return nums[i];
        return nums[nums.length-1];
    }

运行时间10ms。

方法二：哈希

利用HashMap/HashSet，进行一次遍历，若当前哈希表中存在这个数，那么将这个数弹出；若不存在这个数，将它加入HashMap。当遍历结束后，HashMap中唯一留下来的元素就是只出现一次的元素。运行时间21ms。

 public int singleNumber(int[] nums) {
        if(nums.length==1) return nums[0];
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            if(map.containsKey(nums[i])) map.remove(nums[i]);
            else map.put(nums[i],1);
        }
        for(Integer i: map.keySet()) 
             return i;
        return -1;
    } 

注意：这个算法频繁地进行移除操作，另一种写法是可以将HashMap的值维护为count，当这个元素已经存在，将count+1。这样只需要在最后遍历的时候，取到count值为1的元素就可以。

 public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer i : nums) {
            Integer count = map.get(i);
            count = count == null ? 1 : ++count;
            map.put(i, count);
        }
        for (Integer i : map.keySet()) {
            Integer count = map.get(i);
            if (count == 1) {
                return i;
            }
        }
        return -1; // can't find it.
    }

运行时间30ms。

方法三：异或运算

1.如果我们对 0 和二进制位做 XOR 运算，得到的仍然是这个二进制位。
a⊕0 = a
2.如果我们对相同的二进制位做 XOR 运算，返回的结果是 0。
a⊕a=0
3.XOR 满足交换律和结合律。
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
所以我们只需要将所有的数进行 XOR 操作，得到那个唯一的数字。

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