《剑指offer》—— 40. 数组中只出现一次的数字（Java）

推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
   
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
   
        
    }
}

思路：

思路① HashMap

遍历一次数组，用HashMap记录每个数字出现的次数；
再遍历一次数组，找出只出现过一次的数字。

思路② 位运算

将数组中的所有数字全部异或一次。 array[0] ^ array[1] ^ array[2] ^ … ^ array[array.length - 1]
因为
n ^ 0 = n
n ^ n = 0
n1 ^ n2 ^ n3 = n1 ^ ( n2 ^ n3 ) 即满***换律
所以当我们把数组中所有的数字异或之后，出现过两次的的数组就全都被异或成 0 了，相当于是抵消去掉了。最后的结果也就是那两个只出现过一次的数字的异或的结果。
异或结果中的 1 表明了两个只出现过一次的数字的二进制不同的位。我们找出异或结果中第一个 1 的位置的下标 index 。
将数组中所有数字根据二进制中的 index 下标上的位是否为 1 分成两个子数组。两个只出现过一次的数字就会分别到两个子数组中去了。
将这两个子数组分别全部异或，去掉其中出现过两次的数字，最后就分别得到那两个只出现过一次的数字了。

实现：

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
   
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
   
        int length = array.length; 
        //如果array中只有两个数，那么直接分别存到两个结果数组中即可。
        if (length == 2) {
   
            num1[0] = array[0];
            num2[0] = array[1];
            return;
        }
        
        int bitResult = 0;
        //将array数组中的所有数字依次异或，得到两个只出现过一次的数字的异或结果
        for (int i = 0; i < length; ++i) {
   
            bitResult ^= array[i];
        }
        
        //找出异或结果值中的第一个1的下标
        int index = findFirst1(bitResult);
        
        for(int i = 0; i < length; ++i) {
   
            if (isBit1(array[i], index)) {
   
                num1[0] ^= array[i];
            } else {
   
                num2[0] ^= array[i];
            }
        }
    }
    
    //找出第一个1所在位置的下标。
    private int findFirst1(int bitResult) {
   
        int index = 0;
        while (((bitResult & 1) == 0) && index < 32) {
   
            bitResult >>= 1;
            index++;
        }
        return index;
    }
    
    //判断下标 index 上的位是否为 1 。
    private boolean isBit1(int target, int index){
   
        return ((target >> index) & 1) == 1;
    }
    
}

附录：

Java 按位运算符

按位运算符是来操作整数基本数据类型中的单个“比特”(bir)，即二进制位，位运算符会对两个参数中对应的位执行布尔代数运算，并最终生成一个结果。

与（&）
相同为 1 则是 1 ，否则为 0 。
或（|）
有一个为 1 即为 1，全为 0 ，才为 0 .
异或（^）
不同则为 1 ，相同为 0 。
1 ^ 0 = 1
1 ^ 1 = 0
0 ^ 0 = 0

n ^ 0 = n
n ^ n = 0
n1 ^ n2 ^ n3 = n1 ^ ( n2 ^ n3 ) 即满***换律
非（~）
一元操作符，只对一个操作数进行操作。
非1 为 0
非0 为 1

Java 移位操作符

移位操作符操作的运算对象也是二进制的“位”。移位操作符只可用来处理整数类型，左移位操作符（<<）能按照操作符右侧指定的位数将操作符左边的操作数向左移动（在低位补0），“有符号”右移位操作符（>>）则按照操作符右侧指定的位数将操作符左边的操作数向右移。“有符号”右移位操作符使用“符号扩展”；若符号位正，则在高位插入0；若符号位负。则在高位插入1。

Java 中增加了一种“无符号”右移位操作符（>>>）,他使用“零扩展”；无论正负，都在高位插入0。这一操作符是C或C++中所没有的。

例如：

5 >> 2

5 的二进制是 0000 0000 0000 0101

然后右移2位 0000 0000 0000 0001

变成了 1

>>表示右移，如果该数为正，则高位补0，若为负数，则高位补1；

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。