題目描述
一個整型數組里除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。
算法解析： 題目強調了除了兩個數字之外，其他數字都出現了兩次，而我們又知道兩個相同的數異或的結果會被消除，那么如果我們在一個只有一個數字出現了一次，其他數字都出現了兩次的數組中，從頭到尾異或，最后的結果就是這個只出現了一次的數字，但現在是兩個數字，所以如果我們能夠將這個數組分成那樣的兩個子數組，就可以解決這個問題，如果我們從頭到尾將整個數組進行異或，那么最后的結果一定不是0，所以有二進制表示中一位一定為1，我們可以將這一位作為標志位，這一位為1的分為一組，為0的分為一組，則最后就可以分成原型數組。
代碼如下：
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { if (array == null || array.length < 2){ num1[0] = 0; num2[0] = 0; } int temp = 0; for (int i = 0; i < array.length; i++) { temp ^= array[i]; } int pos = 0; String tempString = Integer.toBinaryString(temp); for (int i = tempString.length() - 1; i >= 0; i--) { if (tempString.charAt(i) == '1'){ pos ++; } } ArrayList<Integer> result1 = new ArrayList<>(); ArrayList<Integer> result2 = new ArrayList<>(); for (int i = 0; i < array.length; i++) { if (IsBit1(array[i], pos)){ result1.add(array[i]); }else{ result2.add(array[i]); } } for (int i = 0; i < result1.size(); i++) { num1[0] ^= result1.get(i); } for (int i = 0; i < result2.size(); i++) { num2[0] ^= result2.get(i); } } public boolean IsBit1(int num, int indexBit){ num = num >> indexBit; int result = num & 1; if (result == 0){ return false; } return true; }新聞熱點
疑難解答
