##題目描述 一個整型陣列里除了兩個數字之外，其他的數字都出現了兩次，請寫程式找出這兩個只出現一次的數字，
思路
相同的數異或為0，數字與0異或為其本身，
如果陣列中只出現一次的數字僅一個，將陣列的所有元素異或就可以得到單獨的那個數字，
題目中特地提到只出現一次的數字有兩個，所以需要先將陣列拆分成兩個，每個子陣列里分配一個出現了一次的數字，然后分別異或即為答案：
- 將陣列內所有數字進行異或，因為其他數字都出現了兩次，所以結果為兩個只出現一次數字的異或，
- 兩個不同的數字異或結果中，肯定至少有一位等于1，可以用來區分這兩個數字，并且可以根據該位為0或1將陣列分組，
- 將兩個子陣列所有元素異或，可以找出答案的兩個數，
時間復雜度O(n)，空間復雜度O(1)，
代碼
//num1,num2分別為長度為1的陣列，傳出引數
//將num1[0],num2[0]設定為回傳結果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array == null || array.length < 2) return ;
int tmp = array[0];
for(int i = 1; i < array.length; i++) {
tmp ^= array[i];
}
int flag = 1;
while((flag & tmp) == 0) {
flag <<= 1;
}
num1[0] = 0;
num2[0] = 0;
for(int i = 0; i < array.length; i++) {
if((flag & array[i]) == 0) {
num1[0] ^= array[i];
} else {
num2[0] ^= array[i];
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83483.html
標籤：其他
上一篇：平衡二叉樹
下一篇：和為S的連續正數序列