每日一题《剑指offer》数组篇之数组中只出现一次的两个数字
今日题目链接：数组中只出现一次的两个数字
数组中只出现一次的两个数字
难度：中等
描述
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
数据范围
数组长度 2≤n≤1000，数组中每个数的大小 0<val≤1000000
空间复杂度 O(1)，时间复杂度 O(logn)
举例
解题思路
这道题目相对比较难，一般情况下，我们首先可以想到的是顺序扫描数组，但其时间复杂度为O(n^2)。进一步也可以想到用哈希表保存每一个数次出现的次数，但是这使用了辅助空间，空间复杂度为O(n)。显然均不满足题目要求。
我们先来看一个比较简单的情况，如果数组中只有一个数字出现一次，其他都出现两次。那么我们应该可以想到异或运算。异或运算有一个比较好的性质是：相同为0，相异为1。也就是说， 任何一个数字异或它自己都等于0，而0异或任何数都等于那个数。 因此，我们从头到尾依次异或数组中的每个数字，那么最终结果刚好是那个只出现一次的数字，重复的数字在异或过程中被抵消了。
这是一种比较巧妙的思路，然而，本题只出现一次的数字有两个，简单的异或无法解决。但是，借助这种思路，我们可以进一步分析，如果我们能把数组分成两个子数组，使每个子数组包含一个只出现一次的数字，而其他数字成对出现，那么我们通过上述解法就可以找到两个元素。
具体思路是：我们首先仍然从前向后依次异或数组中的数字，那么得到的结果是两个只出现一次的数字的异或结果，其他成对出现的数字被抵消了。由于这两个数字不同，所以异或结果肯定不为0，也就是这个异或结果一定至少有一位是1，我们在结果中找到第一个为1的位的位置，记为第n位。接下来， 以第n位是不是1为标准，将数组分为两个子数组， 第一个数组中第n位都是1，第二个数组中第n位都是0。这样，便实现了我们的目标。最后，两个子数组分别异或则可以找到只出现一次的数字。
实现代码（java）
以{2,4,3,6,3,2,5,5}为例：
我们依次对数组中的每个数字做异或运行之后，得到的结果用二进制表示是0010。异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1分为两个子数组。第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1，而第二个子数组{4,5,5}中所有数字的倒数第二位都是0。接下来只要分别两个子数组求异或，就能找到第一个子数组中只出现一次的数字是6，而第二个子数组中只出现一次的数字是4。
public class Solution {
public int[] FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
/*
思路：数组中的元素先依次异或，相同为0，则得到的是两个只出现一次的数的异或结果
（因为其他数都是成对出现，所以在异或过程中抵消了）对于得到的异或结果，找到其第
一个为1的位，找到后就可以根据这个位，将两个不同的数分到两个不同的数组，这就找到了。
该位为1，说明两个只出现一次的数该位不同，所以按照该位是0还是1将数组分成两部分
这样，而两个只出现一次的数正好被分开，再各自异或可得结果。
*/
int result=0;
if(array==null||array.length<2)
return result;
for(int num:array) //数组中的元素先依次异或，相同为0，则得到的是两个只出现一次的数的异或结果
result ^= num; //因为数组中其他的数都是成对出现，在异或过程中抵消了，而相同的数异或为0,0跟其他数异或为其他数
//找到两个不相同的数的异或结果result中第一个为1的位，即找到index的位置，因为在这个位置两个数不同【因为“相同为0，相异为1”，而该位为1，说明两个只出现一次的数该位不同，所以按照该位是0还是1将数组分成两部分】
int index=0;
for(;index<32;index++){
if(((result>>index) & 1)==1) //一开始右移0位，然后右移1位，一位一位的找
break;
}
//num1,num2分别为长度为1的数组。分别用来保存两个不同的数，作为返回结果。
//将num1[0],num2[0]设置为返回结果
int[] res = new int[2];
/*按照该位是0还是1将数组分成两部分,分别异或，由于两个出现一次的数在index位上不一样，则可以根据该位将
这两个不同的数放在两个不同的数组上，而由于除这两个数之外的数都是成对出现，在异或过程中被抵消了，所以
不用管其他的数。
*/
for(int num:array){
if(((num>>index)&1)==1)
res[0] ^= num;
else
res[1] ^= num;
}
return res;
}
}腾讯云开发者
