推荐

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

题目描述

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

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

思路:

思路① HashMap

  1. 遍历一次数组,用HashMap记录每个数字出现的次数;

  2. 再遍历一次数组 ,找出只出现过一次的数字。

思路② 位运算

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

实现:

//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 则是 1 ,否则为 0 。

  2. 或 (|)
    有一个为 1 即为 1,全为 0 ,才为 0 .

  3. 异或 (^)
    不同则为 1 ,相同为 0 。
    1 ^ 0 = 1
    1 ^ 1 = 0
    0 ^ 0 = 0

    n ^ 0 = n
    n ^ n = 0
    n1 ^ n2 ^ n3 = n1 ^ ( n2 ^ n3 ) 即满***换律

  4. 非 (~)
    一元操作符,只对一个操作数进行操作。
    非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;

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

这里是猿兄,为你分享程序员的世界。

非常感谢各位大佬们能看到这里,如果觉得文章还不错的话, 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用!!!

注: 如果猿兄这篇博客有任何错误和建议,欢迎大家留言,不胜感激!