算法数据结构奇技淫巧1、找出没有重复的数

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13537.html

这道题可能很多人会用一个哈希表来存储，每次存储的时候，记录 某个数出现的次数，最后再遍历哈希表，看看哪个数只出现了一次。这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13537.html

然而我想告诉你的是，采用位运算来做，绝对高逼格！文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13537.html

我们刚才说过，两个相同的数异或的结果是 0，一个数和 0 异或的结果是它本身，所以我们把这一组整型全部异或一下，例如这组数据是：1， 2， 3， 4， 5， 1， 2， 3， 4。其中 5 只出现了一次，其他都出现了两次，把他们全部异或一下，结果如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13537.html

由于异或支持交换律和结合律，所以:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13537.html

1^2^3^4^5^1^2^3^4 = （1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13537.html

也就是说，那些出现了两次的数异或之后会变成0，那个出现一次的数，和 0 异或之后就等于它本身。就问这个解法牛不牛逼？所以代码如下文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13537.html

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

时间复杂度为 O(n)，空间复杂度为 O(1)，而且看起来很牛逼。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13537.html

作者：帅地
来源：知乎文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13537.html