【试题***】找出落单的数/数组中只出现一次的数
数组中只出现一次的数字
https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
找出落单的数/数组中只出现一次的数
题目：
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解题思想：
异或的特性：0^任意数=任意数，任意数^任意数=0；异或计算的无序性（即1^2^3 = 2^3^1）
1.对原数组所有的数异或得到两个不重复数的异或结果
2.根据两个不重复数的异或结果的二进制位的差异，将原数组分为两组（每组中有一个不重复数）
如：两个数如果分别是 6 和 7
0000 * * * 00 0110
0000 * * * 00 0111
根据原数组中所有数的二进制位最后一位是0或1，将原数组分为两组。
3.再分别对两组数异或
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.ArrayList;
import java.util.Scanner;
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int x = 0;
for(int i = 0; i < array.length; i++){
x ^= array[i];
}
int index = findBitRight1Index(x);
int res1 = 0, res2 = 0;
for(int i = 0; i < array.length; i++){
int temp = array[i];
if( ((temp >> index) & 1) == 0 ){
res1 ^= temp;
}
else{
res2 ^= temp;
}
}
num1[0] = res1;
num2[0] = res2;
}
// 两个数异或结果，从右向左找到差异位，将原来的数组分为两组
public int findBitRight1Index(int number){
int index = 0;
while( (number & 1) == 0 && index < 32){
number >>= (++index);
}
return index;
}
} 
查看8道真题和解析