题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字
思路：首先想到遍历、哈希表等，遍历的话时间复杂度O(n2)，哈希表空间复杂度和时间负责都均为：O(n)，于是，想到了利用位运算去重的方法。
直接上代码：
public class code_3_solution {
/***
* 数组中只出现一次的数字
* 题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字
*/
public static void findNumOnce(int[]arr) {
int num = 0;
for(int i=0;i<arr.length;i++) {
num ^= arr[i];
}
int index = indexOfBit1(num);
int num1=0;
int num2=0;
for (int i=0;i<arr.length;i++) {
if(isBit1(arr[i], index)==0) num1 ^= arr[i];
else num2 ^= arr[i];
}
System.out.println(num1+ ", "+ num2);
}
public static int isBit1(int num, int index) {
return ((num >> (index-1)) & 1);
}
public static int indexOfBit1(int num) {
/**
* 二进制表示时右边第一个为1的位
*/
int index = 1;
while((num & 1) == 0) {
index++;
num = num >>1;
}
return index;
}
public static void main(String[]args) {
int[] arr= {2,4,3,6,3,2,5,5};
findNumOnce(arr);
}
}
