題目描述
一個整型陣列里除了兩個數字之外，其他的數字都出現了兩次，請寫程式找出這兩個只出現一次的數字，
牛客網鏈接
思路
鏈接：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811?f=discussion
來源：牛客網
首先：位運算中異或的性質：兩個相同數字異或=0，一個數和0異或還是它本身，
當只有一個數出現一次時，我們把陣列中所有的數，依次異或運算，最后剩下的就是落單的數，因為成對兒出現的都抵消了，
依照這個思路，我們來看兩個數（我們假設是AB）出現一次的陣列，我們首先還是先異或，剩下的數字肯定是A、B異或的結果，這個結果的二進制中的1，表現的是A和B的不同的位，我們就取第一個1所在的位數，假設是第3位，接著把原陣列分成兩組，分組標準是第3位是否為1，如此，相同的數肯定在一個組，因為相同數字所有位都相同，而不同的數，肯定不在一組，然后把這兩個組按照最開始的思路，依次異或，剩余的兩個結果就是這兩個只出現一次的數字，
java代碼
//num1,num2分別為長度為1的陣列，傳出引數
//將num1[0],num2[0]設定為回傳結果
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int len = array.length;
if (len == 2) {
num1[0] = array[0];
num2[0] = array[1];
return;
}
int bitRes = 0;
for (int i : array) {
bitRes ^= i;
}
int index = findFirst1(bitRes);
for (int j : array) {
if (isBit1(j, index)) {
num1[0] ^= j;
}else {
num2[0] ^= j;
}
}
}
private int findFirst1(int bitRes) {
int index = 0;
while ((bitRes & 1) == 0 && index < 32) {
bitRes >>= 1;
index++;
}
return index;
}
private boolean isBit1(int target, int index) {
return ((target >> index) & 1) == 1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/124303.html
標籤：其他