LeetCode 136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题意：一个数组中，只有一个数出现过一次，其它所有的数字都出现过两次，求哪个数出现过一次。

思路：第一种：用map统计哪个出现过一次
第二种：让所有数字异或，最后得到的结果，就是那个数字

java代码：

public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> dict = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (dict.containsKey(nums[i])) {
                dict.put(nums[i], dict.get(nums[i]) + 1);
            } else {
                dict.put(nums[i], 1);
            }
        }

        for(int i : dict.keySet()){
            if (dict.get(i) == 1) {
                return i;
            }
        }
        return 0;
    }

第二种：

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