一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
示例1
输入
[1,4,1,6]
返回值
[4,6]
说明
返回的结果中较小的数排在前面
public int[] FindNumsAppearOnce (int[] array) {
if (array.length<=2){
return array;
}
//[1,4,1,6]
//[4,6]
///说明
//返回的结果中较小的数排在前面
//先亦或一波,求出数组中只出现过一次的数字的亦或结果
int initNum=array[0];
for (int i = 1; i < array.length; i++) {
initNum^=array[i];
}
int[] res=new int[2];
//求异或结果里最右侧1的位置
int one= initNum-(initNum&(initNum-1));
for (int i = 0; i < array.length; i++) {
//array[0]中陆续存放的相同的2个元素最终会抵消了,剩下的是只出现过一次的且&one等于0的;
if ((one&array[i])==0){
res[0]^=array[i];
}else {
res[1]^=array[i];
}
}
//排序这两个数字
if (array[0]>array[1]){
int temp=array[0];
array[0]=array[1];
array[1]=temp;
}
return res;
}