数组中只出现一次的数字

文章目录

1. 1. 参考

1. 一个整型数组中只有一个数字出现过一次，其他的出现两次，如何找出只出现一次的那个数字？
   解答： 异或运算有一个性质： 任何一个数字异或自己都等于0。
   如果我们将数组中的数字依次异或，最后得到的就是那个只出现一次的数字。

2. 如果一个整型数组只有两个数字只出现一次，其余都出现两次呢？
   解答： 仿照刚刚的思路，将数组拆分成两个子数组：出现两次的数字需要出现在同一个子数组中，而两个只出现一次的数字分别出现在两个子数组中。
   可按如下步骤进行：

   • 将数组中的数字依次异或，最后得到的就是l两个只出现一次的数字的异或结果 a。
   • 记下a 中第一个为 1 的位的位置 n ，因为异或这一位的结果为1，所以两个只出现一次的数字在这一位分别为0和1，故可分到两组中。
     而出现两次的数字两个都将被分到同一组，因为他们的每一位都相同。
   • 分别将两个子数组中的所有数字都异或，即可得到两个只出现一次的数字

参考

[1]： 剑指Offer