题目描述
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
从题目中可以看出来数字出现两次是题目的关键,这里可以利用到异或运算来进行解答。
异或运算:两个相同数字异或=0,一个数和0异或还是它本身。
第一步:通过将数组依次做异或运算,剩下的就是出现一次数字的异或结果。
可能很多人看到这还是不理解将整个数组都遍历一遍相互做异或运算为什么就能把相同的抵消剩下的只是出现一次数字的异或结果。
异或运算还有一个性质: a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;类似乘法的交换律,虽然最终结果都一样,这样的话方便理解。
例如 3 ^ 4 ^ 3 = (3 ^ 3) ^ 4, 其中 3 ^ 3 做异或运算 = 0, 0 在和 4做异或运算不变,当数组出现多对的时候其实可以看成每对两两相互抵消了。
第二步:找出异或结果中二进制为1的位数。
数组异或的结果并不是我们想要的结果,还需要通过这个结果来把数组中的具体数字找出来,这边通过二进制为1的位数来把整个数组区分成2个数组,因为异或运算的结果是值不相同才为1,所以这个异或结果中包含的2个单独出现的数字肯定会分在2个数组中。
第三步:分成的2个数组依次进行异或运算,相互抵消,剩下的即为单独出现的数字,分别在2个数组中。
// 异或运算 (值不相同结果为1,值相同结果为0) public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]){ int bitResult = 0; // 位运算中 异或 的性质:两个相同数字异或=0,一个数和0异或还是它本身。 for(int i=0;i<array.length;i++){ bitResult^=array[i]; } // 相同的异或已经抵消了,结果为单次出现的数字的异或结果 int index = findFrist1(bitResult); for(int i=0;i<array.length;i++){ if(isBit(array[i],index)){ num1[0]^=array[i]; }else{ num2[0]^=array[i]; } } } // 找到第一个二进制为1的位数 public int findFrist1(int bitResult){ int index = 0; while((bitResult & 1) == 0 && index<32 ){ bitResult >>= 1; index++; } return index; } // public boolean isBit(int array,int index){ // 右移index位和1做与运算,即判断array第index位是否为1 return ((array >> index) & 1) == 0; }