LeetCode-136只出现一次的数字

题目描述：

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

分析：

也就是说，一个非空数组中的元素只有一个元素只出现一次，其他都是成对出现的，现在就是要找出这个单飞的元素。

解法：

方法一：使用Set

思路：利用Set接口的特点：相同的值只能插入一次。

将数组里的每一个元素从前往后依次添加到set中，如果返回值是false，则表示set中已经有了该元素，所以将set中的这个元素删掉；反之将元素插入set中。

代码：

class Solution {
        public int singleNumber(int[] nums) {
        Set<Integer> s=new HashSet<>();
        for(int i=0;i<nums.length;i++)
        {
            //如果添加成功了表示只有一个
            //如果添加不成功就把set里边的删掉
            if(!s.add(nums[i]))
            {
                s.remove(nums[i]);
            }
        }
        Object[] o=s.toArray();
        return (int)o[0];
    }
}

分析：该算法的空间复杂度为O(N),时间复杂度为O(N);效率不是很好，但还有另一种比较巧合的方法空间复杂度达到O(1);

方法二：异或

我们都知道异或的结论：相同为0，不同为1

所以比如 [1 2 2 4 1]，如下图异或结果为：4

代码：

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

分析：通过异或的结论来实现该算法空间复杂度为O（1）。