剑指offer系列44---只出现一次 的数字

时间:2022-04-03 16:33:47

【题目】一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
* 【思路】异或性质:数异或自己即为0;
* 一个数组中,从头到尾异或的结果为不重复数字异或结果。成对出现数字异或后抵消。

 package com.exe9.offer;

 /**
* 【题目】一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
* 【思路】异或性质:数异或自己即为0;
* 一个数组中,从头到尾异或的结果为不重复数字异或结果。成对出现数字异或后抵消。
* @author WGS
*
*/
public class FindNumberAppearOnce1 { public void getNumberAppearOnce(int[] arr){
if(arr==null) return ;
int start=0;
//1 先从头至尾依次异或,得到最后的结果。0010(不重复数字异或的结果)
for(int i=0;i<arr.length;i++){
start^=arr[i];
}
//2 由上述得到的结果找到右边第一个1出现的位置;
//int indexOfFirst=findFirstIndexis1(start);
int indexOfOne=0;
while(((start&1)!=1) && (indexOfOne<32)){//位数限制
start=start>>1;
indexOfOne++;//得到位置
}
int num1=0,num2=0;
//3 根据倒数第index位置是否为1将数组arr分成两类,并依次异或,异或的结果即为每个数组中只出现一次的数。
for(int j=0;j<arr.length;j++){
if(isNumOne(arr[j],indexOfOne)){
num1^=arr[j];
}else{
num2^=arr[j];
}
}
System.out.println("只出现一次 的数是:"+num1+","+num2);
}
/*private int findFirstIndexis1(int start) {
int indexOfOne=0;
while(((start&1)!=1) && (indexOfOne<32)){//位数限制
start=start>>1;
indexOfOne++;//得到位置
}
return indexOfOne;
}*/
//判断倒数第indexOfOne位置上是否为1
public boolean isNumOne(int num,int indexOfOne){
num=num>>indexOfOne;
return ((num&1)==1)?true:false; } public static void main(String[] args){
int[] arr=new int[]{2,4,3,6,3,2,5,5};
new FindNumberAppearOnce1().getNumberAppearOnce(arr);
}
}