一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
/** * @author Calvin 2018年5月20日上午10:31:08 * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 */
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
/** * 首先：位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。 * 当只有一个数出现一次时，我们把数组中所有的数， * 依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了 * 。 依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。 * 我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1， * 表现的是A和B的不同的位。我们就取第一个1所在的位数， * 假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。 * 如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数 * 肯定不在一组。然后把这两个组按照最开始的思路，依次异或， * 剩余的两个结果就是这两个只出现一次的数字。 * * * 异或满足交换律和结合律 * * */
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int length = array.length;
if(length == 2){
num1[0] = array[0];
num2[0] = array[1];
return;
}else{
int res = 0;
//把所有的数异或一遍，因为满足交换律和结合律
//相同的数会被抵消
//最后的结果就是2个只出现一次的数字进行异或的结果
for(int i = 0; i < length; ++i){
res ^= array[i];
}
//得到第一个出现的1，因为相同为0，不同为1
//所以这就是2个数字的一个不同的地方，用这个来区分2个数字
int index = findFirst1(res);
for(int i = 0 ; i < length; ++i){
//这1位为1的所有数字，除了目标数字外，都有2个，都会被抵消
//因此最终的结果就是这个目标数字
if(isBit1(array[i], index)){
num1[0] ^= array[i];
}else{
num2[0] ^= array[i];
}
}
}
}
private boolean isBit1(int target, int index){
//判断他的这一位是不是1
return ((target >> index) & 1) == 1;
}
private int findFirst1(int bitResult){
int index = 0;
//找到第一个出现的1，只有这个数字的二进制最后一位为1的时候，&的结果才为0
while(((bitResult & 1) == 0) && index < 32){
bitResult >>= 1;
index++;
}
return index;
}
/** 以下为牛客ID 高琥所写 */
/** * 数组中有两个出现一次的数字，其他数字都出现两次，找出这两个数字 * @param array * @param num1 * @param num2 */
public static void findNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array == null || array.length <= 1){
num1[0] = num2[0] = 0;
return;
}
int len = array.length, index = 0, sum = 0;
for(int i = 0; i < len; i++){
sum ^= array[i];
}
for(index = 0; index < 32; index++){
if((sum & (1 << index)) != 0) break;
}
for(int i = 0; i < len; i++){
if((array[i] & (1 << index))!=0){
num2[0] ^= array[i];
}else{
num1[0] ^= array[i];
}
}
}
/** * 数组a中只有一个数出现一次，其他数都出现了2次，找出这个数字 * @param a * @return */
public static int find1From2(int[] a){
int len = a.length, res = 0;
for(int i = 0; i < len; i++){
res = res ^ a[i];
}
return res;
}
/** * 数组a中只有一个数出现一次，其他数字都出现了3次，找出这个数字 * @param a * @return */
public static int find1From3(int[] a){
int[] bits = new int[32];
int len = a.length;
for(int i = 0; i < len; i++){
for(int j = 0; j < 32; j++){
bits[j] = bits[j] + ( (a[i]>>>j) & 1);
}
}
int res = 0;
for(int i = 0; i < 32; i++){
if(bits[i] % 3 !=0){
res = res | (1 << i);
}
}
return res;
}
}