一、题目描述

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

说明：

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

示例 1:

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

示例 2:

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

二、思路讲解与代码实现

首先很容易想到的是排序，排序了之后，只存在一个的数字（后面简称为目标数字）的左右必然都不是与他相等的数字。

这个时候需要考虑目标数字在最前面或最后面的情况，需要单独处理。

class Solution {
    public int singleNumber(int[] nums) {

        if(nums.length==1){
            return nums[0];
        }
        Arrays.sort(nums);

        int len = nums.length;
		
		//当目标数字在第一个的时候
        if(nums[0]!=nums[1]){
            return nums[0];
        }
        for(int i=1; i<len-3; i++){
			//如果一个数跟他左右的元素都不一样，则是我们要找的数
            if(nums[i]!=nums[i+1]){
                if(nums[i+1]!=nums[i+2]){
                    return nums[i+1];
                }
            }
        }
		//当目标数字在最后一个的时候
        if(nums[len-1]!=nums[len-2]){
            return nums[len-1];
        }
        return 0;
    }
}

时间复杂度： O(NlogN)

空间复杂度： O(1)

排序的时间复杂度有些过高了，我们如何能够通过一遍遍历就能够找到目标数呢？

可以使用HashSet或HashMap。

使用 HashMap 可以记录每个数字的出现次数，然后找到次数为1的即可。

使用 HashSet 时，如果遇到重复数字不能添加的情况，就把set中的那个重复数字也删去。因为一个数字最多出现两次，出现第二次的时候没有添加进set，并且还把第一次的添加给删掉了，所以set最后只会留下这个只出现过一次的数字。

下面是使用set的实现：

class Solution {
    public int singleNumber(int[] nums) {

        Set<Integer> set = new HashSet<>();

        for(int i=0;i<nums.length; i++){
            //如果重复了，就把原本set里的那个元素也删掉  删到最后只会剩下一个元素，就是单个的那个元素
            if(!set.add(nums[i])){
                set.remove(nums[i]);
            }
        }
        //此时set中只有一个元素
        for(Integer i : set){
            return i;
        }
        return 0;
    }
}

时间复杂度： O(N)

空间复杂度： O(N)

这个方法需要使用线性级的空间，我们可不可以再做一下优化，如何在只遍历一遍的情况下，只使用常量级的空间呢？

这就需要使用异或运算了。我们知道，两个相同的数进行异或运算，结果为0，而0和任意不是0的数字异或，结果仍是这个数字。那么我们就将所有的数字进行异或运算，每个出现两次的数字都抵消为0，最后得到的结果就是目标数了。

class Solution {
    public int singleNumber(int[] nums) {

        int res = 0;
        for(int num : nums){
            res = res ^ num;
        }
        return res;
    }
}

时间复杂度： O(N)

空间复杂度： O(1)

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125000.html