Leetcode-136-只出现一次的数字

给定一个整数数组，除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。

备注：

你的算法应该是一个线性时间复杂度。 你可以不用额外空间来实现它吗？

---

分析：

这是一道著名的面试题，题意明显，所有的元素都是成对出现的，只有1个元素是单身。

解法一：

很容易想到的解决办法就是把数组排序，相同的元素会前后挨着，正常情况下脚标为0和1的两个元素相同，2和3两个元素相同，直到那个单身的元素出现才会扰乱这个局面，就这样当出现两个元素不相同的时候，前一个元素就是要找的单身元素。
这种解法虽然可以找出单身元素，但是要使用排序，排序的时间复杂度是O(nlogn)，不是线性时间复杂度（O(n)），不符合平台的要求。

    public int singleNumber(int[] nums) {
        if (nums.length == 0) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0];
        }

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

解法二：

第二种解法可以完美的解决这个问题。使用的是异或的方法。
先简单的介绍一下异或。异或是二元运算符，必须要有两个元素参与运算。
异或简单的说：两者的值不同返回true，两者的值相同返回false。

真值表.png

异或的特性：

1.恒定律：A ^ 0 = A
2.归零率：A ^ A = 0
3.交换律：A ^ B = B ^ A
4.结合律：(A ^ B) ^ C = A ^ (B ^ C)

异或可以做的事情：

异或可以快速比较两个值是否相等 a ^ b == 0，效率非常高，比 a - b == 0 高很多。

异或还能在不定义临时变量的情况下，交换两个值（经典题目）
a = a ^ b
b = a ^ b // a ^ b ^ b = a ^ 0 = a
a = a ^ b // a ^ b ^ a = b ^ 0 = b

好了，现在利用学习的异或知识，来分析一下这道题。
假设所有的数组为：abcbcda
a ^ b ^ c ^ b ^ c ^ d ^ a
= a ^ a ^ b ^ b ^ c ^ c ^ d
= 0 ^ 0 ^ 0 ^ d
= d
很神奇是不是？这个的时间复杂度为O(n)，是线性的，空间复杂度是O(1)

Java代码如下：

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

参考博客：https://www.lijinma.com/blog/2014/05/29/amazing-xor/