只出现一次 的数字

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

说明：

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

示例 1:

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

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

这道题如果不限制时间和空间的复杂度其实有很多种解法，接下来我们着重讲三种做法，不在于结果而在于解决这个问题过程种的分析
一、利用hashMap对应存储每个数字的次数，最后取出次数为1的数字，但时间复杂度为o（n）

class Solution {
    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; 
    }
}

二、我们如果利用暴力方法对每一个数组在后面的集合中查找时间复杂度为o(n^2),但我们思索一下，如果我们将数组排序一下，就可以讲复杂度降到o(n),且是线性复杂度

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

三、接下来的方法非常牛，利用位运算来解决问题，接下来就来分析一下位运算，以及如何利用位运算来解决这个问题,由于输入问题我们用#代替^符号
首先我们来理解一下或与运算符的规则，位运算有以下三种性质
即根据操作数的二级制数来运算，对应位相同则为0，不同则为1，利用这个衍生处三个性质
1.任何与0做位运算的数字结果都为数字本身：0#a=a
2.任何数于本事做位运算结果都为0:a#a=0
3.位运算满足交换律和结合律即:a#b=b#a,a#b#c#d=(a#b)#(c#d)
所以我们利用上述的结论，对数组进行分析，我们假设该数组有2*m+1个数字，其中m组数组均为出现2次，剩余一个数字出现1次，那么我们总可以将这个数组化成下列形式
(a1#a1)#(a2#a2)……(am#am)#am+1,其中成对的结果都为0最终就是0#am+1就是只出现了一次的数字

public static int singleNumber2(int [] nums) {
		int res = 0;
		for(int num:nums) {
			res^=num;
		}
		return res;
	}