数组中只出现一次的数字
-
- 题目描述
- 思路
- 题解
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路
这道题是典型的2n+2的问题，是2n+1问题的变种。
我们不如先来看，如何解决2n+1的问题：
一个整型数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。
我们可以利用异或运算的性质来求解：
0^a = a; 1^a = ~a; a^a = 0;
所以可以想见。如果我们将数组中所有元素的值相异或，其中两两成对的会得到结果0，而任何数与0异或得到的结果是其本身。此时，最终结果也就是落单的数与无数个0异或的结果，得到的结果值就是该落单的数的值。
我们已经利用异或的性质巧妙解决了2n+1的问题，时间复杂度为O(n)，空间复杂度为O(1)。
那么我们能否将同样的方法应用于2n+2的问题呢？
同样思考，如果将所有元素相异或，得到的结果是什么？是落单的两个数相异或的值：a^b。
那么a^b有什么性质呢？我们如何通过该值获取a和b的信息？
认真分析题意，我们会发现还有一个隐含条件可以为我们利用，即a和b是不同的数。既然如此，a^b的值就不可能为0。一定至少有一位（二进制表示）的值为1。而a和b在该位上恰好不同。
不妨以该位上的值为依据，将2n+2的数分为两组：2x+1和2y+1。（毕竟相同的数每一位都相同，所以可以保证成对的数最终被分到同一个组）。
此时2n+2的问题就被分解成了两个2n+1的问题，按照以上的方法分别求解即可。
题解
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int result=0;
int i=0;
for(i=0;i<array.length;i++){
result ^= array[i];
}
i=0;
while(result>0){
if(result%2==1){
break;
}else{
result = result>>1;
i++;
}
}
int j = 1<<i;
for(i=0;i<array.length;i++){
if((array[i]&j)==0){
num1[0] ^= array[i];
}else{
num2[0] ^= array[i];
}
}
}
}