題目：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次护盈。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字挟纱。
//num1,num2分別為長度為1的數(shù)組。傳出參數(shù)
//將num1[0],num2[0]設(shè)置為返回結(jié)果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array.length < 2){
return;
}
int n = 0;
for(int i = 0; i < array.length; i++){
n ^= array[i];
}
int last = n - ((n - 1) & n);
for(int i = 0; i < array.length; i++){
if( ( last & array[i]) == 0){
num1[0] ^= array[i];
}else{
num2[0] ^= array[i];
}
}
}
}
- 兩個(gè)同樣的數(shù)相異或后等于0
- 兩個(gè)一樣的數(shù)a的和一個(gè)不一樣b的數(shù)相異或后 （a ^ b ^ a）結(jié)果為b腐宋，并且與順序無關(guān)
- a ^ b ^ c ^ d ^ e ^ d ^ c ^ b ^ a = e
- 利用這個(gè)條件紊服，我們將所有的數(shù)都異或一遍，將得到要求的兩個(gè)數(shù)相&的結(jié)果胸竞。（a ^ b ^ c ^ d ^ a ^ d = b ^ c）
- 然后利用一個(gè)公式求出b和c之間的一個(gè)有差異的位欺嗤，并按照這個(gè)位的值不同，將數(shù)組分為兩組（aca卫枝，bdd） 然后分別再分別在兩個(gè)組里全部相異或一次（a ^ c ^ a, b ^ d ^ d）
- 這個(gè)表示差異的位的信息存在last里面煎饼，last是用來求一個(gè)二進(jìn)制數(shù)的最后一個(gè)1的位置的算法（n = 10001100，(n - 1) & n= 10001000校赤，last = 100）
