只出现一次的数字

leetCode–136(只出现一次的数字)

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

说明：

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

示例 1:

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

示例 2:

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

解法一：自己

利用Hash表进行计算，使用一个map来存储数据 key：数的大小 value：该数的个数，再遍历map。值为1 的就是结果。

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

解法二：排序+遍历

class Solution {
    //排列
    public int singleNumber(int[] nums) {
        int n = nums.length;
        if (n<=1) return nums[0];
        //数组进行排序
        Arrays.sort(nums);
        //排序后进行遍历
        for (int i = 0;i<n;i=i+2){
            //如果已经遍历到最后一个元素，则最后一个元素就是结果
            if (i==n-1) return nums[i];
            if (nums[i]!=nums[i+1]) return nums[i];
        }
        return -1;
    }
}

解法三：异或 简直妙妙妙！！

打死我也想不到用这种方法，简直是太牛了！！！

这也是为什么要记录这题的原因，太妙了！！要记住哈~~

异或运算有以下三个性质：

• 任何数和 0 做异或运算，结果仍然是原来的数， 即 a ⊕ 0 = a
• 任何数和其自身做异或运算，结果是 0 ，即 a ⊕ a = 0
• 异或运算满足交换律和结合律,即a ⊕ b ⊕ a = b ⊕ a ⊕ a = b ⊕ (a ⊕ a) = b ⊕ 0 = b

有了以上三个性质，可以得出—->所有的数异或之后所得的数就是结果，因为其他的数两两相等，异或为0，0再和一个元素异或等于本身！

代码为：

class Solution {
    //异或
    public int singleNumber(int[] nums) {
        int n = nums.length;
        if (n<=1) return nums[0];
        int res = nums[0];
        for (int i = 1;i<n;i++){
            res = res^nums[i];
        }
        return res;
    }
}