【LeetCode】查找只出现一次的数字算法

题目要求

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

（LeetCode136也就是这么个题吧，简单题，要求是最好写出线性的时间复杂度和O(1)的空间复杂度）

分析

首先很容易想的就是开一个数组计数，但算法效率肯定不好。 还可能用哈希什么的去做，线性的空间能保证吗？ …… 其实这问题本质上是考察 按位异或 的位运算符的。

怎么说？ 学过离散数学我们知道，异或是说，同则取0，异则取1。 按位异或就是按照二进制的表示，两个数每一位同则取0，异则取1。 异或也有交换律：a ^ b = b ^ a，所以顺序无所谓的。 既然其他数都是出现两次，那我们就可以认为遍历结束后的时候，每个两两相同的数值对异或后都是0了，剩下的是那个落单的。 怎么让结果就是落单的呢？ 还得从0身上下手： a ^ 0 = a 所以说，只要初值设成0的话，遍历一趟数组，逐一异或，最终结果就是出现一次的数。

Java编程实现

class Solution {
    public int singleNumber(int[] nums) {
        int n = 0;
        for (int i : nums) {
            n ^= i;
        }
        return n;
    }
}