剑指offer 记录

040-数组中只出现一次的数字

这篇文章中介绍了两种方法，暴力解析法和全局异或法，详情可以查看博客。 对于这两种解法的缺点在以下指出，如果有不对之处，可以提醒我一下。

暴力解析

原理

循环整个数组，记录每一个数据出现的次数，然后重新循环数据次数数组，找出出现一次的数字

结果

需要重新创建一个缓冲区来记录当前数组内的每个数字出现的次数，浪费空间。 需要循环两次数组，时间浪费。

全局异或

原理：

创建一个全局变量，根据异或规则–>异或两次结果为0，所以如果有存在两个相同数字进行异或操作的话，则可以认为微操作。则实际上进行异或操作的只有出现一次的两个数字。 根据最终结果的其中一个1的位置，将数字分为此位置为1的数字数组和此位置不是1的数字数组，则两个数字分别在两个数组内。 重新使用异或运算，则可以找到这两个数字。

结果

需要计算整个数组的异或结果，且最终也需要重新遍历数组，来寻找两个数字。

本文提供了另一个思路，但是只适用于数组内数字不大于31的情况。

原理

使用两次异或结果为0的原理，将数字转换为一个32位数字的位上，循环一遍数组，最终会在结果数字的两个位上数字是1，寻找这两个置1的位的位置信息，则可以找到单次出现的数字。

只适用于数组内数字比较小的时候