題目：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外帖世，其他的數(shù)字都出現(xiàn)了兩次笨奠。請(qǐng)寫(xiě)程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字
思路：首先想到遍歷假夺、哈希表等，遍歷的話時(shí)間復(fù)雜度O(n2)哪工，哈希表空間復(fù)雜度和時(shí)間負(fù)責(zé)都均為：O(n)奥此，于是弧哎，想到了利用位運(yùn)算去重的方法。
直接上代碼：
public class code_3_solution {
/***
* 數(shù)組中只出現(xiàn)一次的數(shù)字
* 題目描述：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次祥绞。請(qǐng)寫(xiě)程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字
*/
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) {
/**
* 二進(jìn)制表示時(shí)右邊第一個(gè)為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);
}
}
