题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
算法解析： 题目强调了除了两个数字之外，其他数字都出现了两次，而我们又知道两个相同的数异或的结果会被消除，那么如果我们在一个只有一个数字出现了一次，其他数字都出现了两次的数组中，从头到尾异或，最后的结果就是这个只出现了一次的数字，但现在是两个数字，所以如果我们能够将这个数组分成那样的两个子数组，就可以解决这个问题，如果我们从头到尾将整个数组进行异或，那么最后的结果一定不是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; }新闻热点
疑难解答
