题目描述
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
代码语言：javascript复制示例1
输入
[1,4,1,6]
返回值
[4,6]
说明
返回的结果中较小的数排在前面思路:
- 1.首先全数组异或找出这个数组中不同的两个数字的异或结果 initNum 原理:相同数字的异或结果为0(异或 每一位相同则置0不同则取1)
- 2.由于异或结果是我们要求的两个不同数字的异或结果,那么我们可以找到最后一个1的位置,这两个数在此位置上必然一个是0一个是1(异或特性).
- 3.找到最后可以1的位置后,利用两个数字在此位置上必然是一个是0一个是1,我们可以利用与特性区分这两个数字的位置.另外其他相同数字不管落在数组中哪个位置上,两个相同数字的异或结果必然是0,因此最后落到我们数组中的必然两个不同的数字.
- 4.由于不清楚这两个数字落的位置,因此咱们还要排序一波
代码:
代码语言：javascript复制 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;
}
