算法8 只出现一次的数字 leetcode136

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:

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

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

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x21ib6/

想法

看起来很简单，确实很简单，但是没想到用新的方法（异或、set）
其实还可以按奇偶位置来做。。。

XOR、SET

//a^a=0；自己和自己异或等于0

//a^0=a；任何数字和0异或还等于他自己

//a^b^c=a^c^b；异或运算具有交换律

//有了这3个规律，这题就很容易解了，我们只需要把所有的数字都异或一遍，最终的结果就是我们要求的那个数字。来看下代码


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

public int singleNumber(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (!set.add(num)) {
            //如果添加失败，说明这个值
            //在集合Set中存在，我们要
            //把他给移除掉
            set.remove(num);
        }
    }
    //最终集合Set中只有一个元素，我们直接返回
    return (int) set.toArray()[0];
}

作者：数据结构和算法
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x21ib6/?discussion=LIRNfM
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的原始方法

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