剑指Offer | 数组中只出现一次的数字-蒲公英云

剑指Offer | 数组中只出现一次的数字

r囧r小猫 2022-05-23 07:35 261阅读 0赞

做了个剑指Offer的题目目录，链接如下：
https://blog.csdn.net/mengmengdastyle/article/details/80317246

一、题目

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
测试用例:
[2,4,3,6,3,2,5,5]
对应输出应该为:
“4,6”
暴力破解，就不解释了。讲一下用位运算的方法

二、与、或、异或运算

1.与运算（&）
运算规则：0&0=0; 0&1=0; 1&0=0; 1&1=1;
即：两位同时为“1”，结果才为“1”，否则为0

例如：3&5 即 0000 0011 & 0000 0101 = 0000 0001 因此，3&5的值得1。
例如：9&5 即 0000 1001 (9的二进制补码)&00000101 (5的二进制补码) =00000001 (1的二进制补码)可见9&5=1。

2.或运算（|）
参加运算的两个对象，按二进制位进行“或”运算。
运算规则：0|0=0； 0|1=1； 1|0=1； 1|1=1；
　　即：参加运算的两个对象只要有一个为1，其值为1。
例如:3|5　即 0000 0011 | 0000 0101 = 0000 0111 因此，3|5的值得7。　

例如：9|5可写算式如下： 00001001|00000101 =00001101 (十进制为13)可见9|5=13

3.异或运算（^）

参加运算的两个数据，按二进制位进行“异或”运算。
运算规则：0^0=0； 0^1=1； 1^0=1； 1^1=0；

　　即：参加运算的两个对象，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。
例如：9^5可写成算式如下： 00001001^00000101=00001100 (十进制为12)可见9^5=12

三、讲解

如输入数组为：{2,4,3,6,3,2,5,5}

除了有两个数字只出现了一次，其他数字都出现了两次。异或运算中，任何一个数字和自己本身异或都是0，任何一个数字和0异或都是本身。
所以：将数组中的数都异或运算后，相同的数字将被消除，得到得是只出现一次的两个数字的异或运算。

0^2^4^3^6^3^2^5^5 = 4^6 = 0100 ^ 0110 = 0010 = 2

2.记 flag=0010；
从右向左找，找到1。

只出现一次的两个数字4（0100）和6（0110），从右向左第一个不同的数字为右边第二位；
根据这个条件可以将整个数组分成两部分，

flag & array[i]

看运算及分组图示：
这里写图片描述

5.将两组数分别再分别异或运算，相同的数异或后为0；
即可得到两个数组中只出现一次的数字，4和 6；

四、代码

public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        //如array={2,4,3,6,3,2,5,5}
        if(array.length < 2) return ;
        int myxor = 0;  //用0，因为0与任何数 异或后 都为 任何数
        //将数组中的数都异或运算后，相同的数字将被消除，得到得是只出现一次的两个数字的异或运算。
        for(int i = 0 ; i < array.length; ++ i ){   
            myxor ^= array[i];  //最后得到的是 4和6的异或
        }
        //4^6 = 0100 ^ 0110 = 0010 
        int flag = 1;   //用来从右到左找哪个位首先不同
        while((myxor & flag) == 0){         
            flag <<= 1; //左移一位，直到找到为 flag=0010；
        }
        for(int i = 0; i < array.length; ++ i ){    
            if((flag & array[i]) == 0){ //以flag分组
                num2[0]^= array[i];
            }else{
                num1[0]^= array[i];
            }
        }
    }
}