560，位运算解只出现一次的数字 II

2023-11-20 11:59:09

A lie can travel halfway around the world while the truth is still putting on its shoes.

当真理还正在穿鞋的时候，谎言就能走遍半个世界。

问题描述

来源：剑指 Offer 56 - II

难度：中等

在一个数组nums中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]

输出：4

示例 2：

输入：nums = [9,1,7,9,7,9,7]

输出：1

限制：

1 <= nums.length <= 10000
1 <= nums[i] < 2^31

使用HashMap

这题说的很明白，只有一个数字出现了一次，其他的数字都出现了3次，找出那个出现一次的数字。最简单的一种方式就是使用HashMap统计每个数字出现的次数，因为只有一个数字出现一次，其他都出现3次，我们只需要返回那个出现一次的即可，原理比较简单，来看下代码

 1public int singleNumber(int[] nums) {
 2    Map<Integer, Integer> map = new HashMap<>();
 3    //先把数字存储到map中，其中key存储的是当前数字，value是
 4    //数字的出现的次数
 5    for (int num : nums) {
 6        map.put(num, map.getOrDefault(num, 0) + 1);
 7    }
 8    //最后在遍历map中的所有元素，返回value值等于1的
 9    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
10        if (entry.getValue() == 1)
11            return entry.getKey();
12    }
13    return -1;
14}

位运算解决

在java中int类型是32位，我们需要统计所有数字在某一位置的和能不能被3整除，如果不能被3整除，说明那个只出现一次的数字的二进制在那个位置是1……把32位全部统计完为止，来看个视频

再来看下代码

 1public int singleNumber(int[] nums) {
 2    //最终的结果值
 3    int res = 0;
 4    //int类型有32位，统计每一位1的个数
 5    for (int i = 0; i < 32; i++) {
 6        //统计第i位中1的个数
 7        int oneCount = 0;
 8        for (int j = 0; j < nums.length; j++) {
 9            oneCount += (nums[j] >>> i) & 1;
10        }
11        //如果1的个数不是3的倍数，说明那个只出现一次的数字
12        //的二进制位中在这一位是1
13        if (oneCount % 3 == 1)
14            res |= 1 << i;
15    }
16    return res;
17}

这题我们还可以扩展一下

一，如果只有一个数字出现一次，其他数字都出现偶数次，我们只需要把所有数字异或一遍即可。

因为异或有下面几条性质

a^a=0 任何数字和自己异或结果是0
a^0=a 任何数字和0异或还是他自己
a^b^c=a^c^b 异或运算具有交换律

二，如果只有一个数字出现一次，其他数字都出现奇数次，我们可以用下面代码来解决。

 1// n是出现的次数
 2public int findOnce(int[] nums, int n) {
 3    int bitLength = 32;
 4    int res = 0;
 5    for (int i = 0; i < bitLength; i++) {
 6        int oneCount = 0;
 7        for (int j = 0; j < nums.length; j++) {
 8            oneCount += (nums[j] >>> i) & 1;
 9        }
10        if (oneCount % n != 0)
11            res |= (1 << i);
12    }
13    return res;
14}

状态机1

按照题意的要求，我们定义一种运算如果某个数出现3次，通过这种运算就让他的结果变成0，也就是说周期是3。每个数都会有下面几种状态

出现0次
出现1次
出现2次
出现3次

因为周期是3，当出现3次的时候可以认为出现了0次，也就是下面几种状态

出现0次
出现1次
出现2次

看到这里其实大家已经想到了，这不就是传说中的3进制吗。

在二进制中一个位置要么是1要么是0，只能表示一种状态，如果要表示3种状态我们可以使用两位数字来表示

我们选择

00表示出现0次
01表示出现1次
10表示出现2次

但这里好像没有出现3次的，其实上面已经说了，出现3次的可以认为是出现0次。对于每一个数字，如果是0我们就不用了管他，只有是1的时候状态才会改变（这里数字展示会出现错乱，下面全是截图，如果看不清楚，可以点击放大）

来看下代码

 1public int singleNumber(int[] nums) {
 2    int a = 0, b = 0;
 3    for (int c : nums) {
 4        //防止a的值被修改，在计算b的时候有影响，
 5        //这里在b计算完之后再对a赋值
 6        int tempa = ~a & b & c | a & ~b & ~c;
 7        b = ~a & ~b & c | ~a & b & ~c;
 8        a = tempa;
 9    }
10    return b;
11}

状态机2

上面我们选择的是00，01，01三种状态。那么能不能选择其他状态能，当然是可以的，比如我们选择00，01，11三种状态

来看下代码

 1public int singleNumber(int[] nums) {
 2    int a = 0, b = 0;
 3    for (int c : nums) {
 4        //防止a的值被修改，在计算b的时候有影响，
 5        //这里在b计算完之后再对a赋值
 6        int tempa = ~a & b & c | a & b & ~c;
 7        b = ~a & ~b & c | ~a & b & c | ~a & b & ~c | a & b & ~c;
 8        a = tempa;
 9    }
10    return b;
11}

状态机3

除了上面提到的使用两位数字，难道就不能使用三位数字吗，当然也是可以的，比如我们使用3个数字001，010，100来表示，我们来看一下

来看下代码

 1public int singleNumber(int[] nums) {
 2    //因为默认是001，所以c的位置我们让他全部变为1
 3    int a = 0, b = 0, c = - 1;
 4    for (int d : nums) {
 5        int tempa = ~a & b & ~c & d | a & ~b & ~c & ~d;
 6        int tempb = ~a & ~b & c & d | ~a & b & ~c & ~d;
 7        c = a & ~b & ~c & d | ~a & ~b & c & ~d;
 8        a = tempa;
 9        b = tempb;
10    }
11    return b;
12}

看到这里大家是不是有想法了，上面选择两位，三位都可以计算，那么四位能不能计算呢，其实也是可以的。在java中int是32位，只要不是选择1位，无论你选择2位还是28位还是32位其实都是可以的，只要满足让他出现3次的时候回到初始状态即可。那这样写下去答案就比较多了，这里就不在一直往下写了,如果感兴趣的大家可以试着写下。

总结

之前我在LeetCode上写这题解的时候，很多同学评论不知道公式怎么推导的，这里再来补充一下

其实公式的推理很简单，就拿我上面写的状态机2来说