算法数据结构规则 1. 找出不重复的数字

1。查找不重复的数字

给你一组整数数据。在这些数据中，一次仅出现一个数字。其他数字出现两次，让您可以看到数字。

很多人可能会用标签表来存储这个问题。每次存储时，记录某个数字出现的次数，最后检查哈希表，看看哪个数字只出现一次。该方法的时间复杂度为O(n)，空间复杂度为O(n)。

不过，我想告诉大家的是，用位运算来做到这一点是非常先进的！

我们刚才说了，两个相同的数字异或的乘积是0，而一个数字和0异或的乘积是它本身，所以这些数字都是异或。比如这个数据集是：1,2,3,4,5,1,2,3,4。其中5只出现了一次，其他出现了两次。都是异或，结果如下：

因为异或支持交换律和结合律，所以为：

1^2^3^4^ 5^1^2^3^ 4 = (1 ^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5.

换句话说，出现两次的数字异或后会变成0，而与0异或后出现一次的数字就是它本身。请问，这个方案好吗？所以这是代码

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)，太棒了。

作者：帅迪
来源：知乎