漫画：位运算系列篇（只出现一次的数字

今天是小浩算法“365刷题计划”第63天。今天状态不好，因为昨天感冒了，写了好久才写下这篇长文，本来说写点别的水一水，改天再做这个续集，但是想了想还是算了！昨天我们在“除了某个元素只出现一次以外，其余每个元素均出现二次”的条件下，通过使用“异或”的操作，找到了只出现一次的元素。那对于其余每个元素均出现三次的case，我们应该如何解决呢？一起来看下，原题如下：

看之前强烈建议复习昨天的文章：

漫画：位运算系列篇（只出现一次的数字）

01

PART

Single Number Ⅱ

这种通过改变题中条件，进而增加难度的方式，其实是出题者惯用的一种手段！

第137题：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

（瞪一瞪就全部掌握）

PS：建议大家停留个两分钟先想一想...直接拉下去看题解就没什么意思了。

02

PART

HashMap求解

很简单就能想到，说白了就是统计每个元素出现的次数，最终再返回次数为1的元素。但是使用了额外空间。

直接上代码：（go版本）

<code> 1func singleNumber(nums []int) int {
 2    m := make(map[int]int)
 3    for _, k := range nums {
 4        //如果是其他语言，请注意对应的判空操作！
 5        m[k]++
 6    }
 7    for k, v := range m {
 8        if v == 1 {
 9            return k
10        }
11    }
12    return 0
13}/<code>

（并不怎么样）

郑重申明（读我的文章必看）：

• 本系列所有教程都不会用到复杂的语言特性，不需要担心没有学过相关语法，使用各语言纯属本人爱好。
• 作为学术文章，虽然风格可以风趣，但严谨，我是认真的。本文所有代码均在leetcode上进行过测试运行。
• 算法思想才是最重要的。

03

PART

数学方式

这个题目曾经在Google很火~目前国内应该也有很多厂子会问到。

原理：[A,A,A,B,B,B,C,C,C] 和 [A,A,A,B,B,B,C]，差了两个C。即：

3×(a+b+c)−(a+a+a+b+b+b+c)=2c

也就是说，如果把原数组去重、再乘以3得到的值，刚好就是要找的元素的2倍。举个例子：

利用这个性质，进行求解：（python代码如下，这里要注意的是，使用int可能会因为超出界限报错）

<code>1class Solution:2    def singleNumber(self, nums: List[int]) -> int:3        return int((sum(set(nums)) * 3 - sum(nums)) / 2)/<code>

(效果不错，但是仍然使用了额外空间)

04

PART

位运算

对于“每个其余元素，均出现了二次”之所以可以使用“异或

这个思想可能比较简单，但是要让大家理解，还是有一定难度。如果大家准备好了，可以开始往下看。我看过leetcode上的题解，很多都是直接扔出来一个公式，其实讲的我认为并不是特别的清楚。所以我打算先把本题退化到“每个其余元素，均出现二次”的case来进行分析一下。

假如我们有 [21,21,26] 三个数，是下面这样：

回想一下，之所以能用“异或”，其实我们是完成了一个 同一位上有2个1清零 的过程。上面的图看起来可能容易，如果是这样：

那对于“每个其余元素，均出现了三次”也是一样，如果我们可以完成 一个同一位上的三个1清零的过程，也就是 a ？a ？a = 0，问题则迎刃冰解。那因为各语言中都没有这样一个现成的方法可以使用，所以我们需要构造一个。（想象一下，位运算也是造出来的对不对？）

如何构造，这里先说第一种方法（注意，到这里我们的问题已经转化成了定义一种 a ? a ? a = 0 的运算），观察一下“异或”运算：

1^1=0

1^0=1

0^1=1

是不是可以理解为，其实就是二进制的加法，然后砍掉进位呢？

砍掉进位的过程，是不是又可以理解为对 2 进行取模，也就是取余。到了这里，问题已经非常非常明确了。那我们要完成一个 a ? a ? a = 0 的运算，是不是其实就是让其二进制的每一位数都相加，最后再对 3 进行一个取模的过程呢？（一样，如果要定义一个 a ? a ? a ? a = 0 的运算，那就最后对 4 进行取模就可以了）

<code> 1//go
 2func singleNumber(nums []int) int {
 3    number, res := 0, 0
 4    for i := 0; i  5        //初始化每一位1的个数为0
 6        number = 0
 7        for _, k := range nums {
 8            //通过右移i位的方式，计算每一位1的个数
 9            number += (k >> i) & 1
10        }
11        //最终将抵消后剩余的1放到对应的位数上
12        res |= (number) % 3 <13    }
14    return res
15}/<code>

如果对上面的代码不能理解，可以看看这个图，假设只有一个数 [21]，我们通过不断右移的方式，获取其每一位上的1。当然，这里因为余数都是1，所以肯定都保留了下来，然后与 1 进行 “与”运算，最终再将其放入到对应的位数上。

（还不错）

在上面的代码中，我们通过一个number，来记录每一位数出现的次数。但是缺点是，我们记录了64位（Go语言中，int为32位以上）

（官方文档）

那如果我们可以同时对所有位进行计数，是不是就可以简化过程。因为我们的目的是把每一位与3取模进行运算，是不是就可以理解为其实是一个三进制。如果大家听不懂三进制的话，可以简单理解为3次一循环，也就是 00 - 01 - 10 - 11。但是又因为对于 11 这种情况，我们需要砍掉（上面已经说过了，相当于 11 - 00 的转化），所以我们就只有3个状态，00 - 01 - 10，所以我们采用 a 和 b 来记录状态。其中的状态转移过程如下：

这里 a` 和 b` 的意思代表着 a 和 b 下一次的状态。next 代表着下一个 bit 位对应的值。然后这是什么，不就是状态机嘛。。。我们通过 a 和 b 的状态变化，来完成次数统计。

然后因为此图复杂，将其分别简化成 a 和 b 的卡诺图（卡诺图是逻辑函数的一种图形表示。两逻辑相邻项，合并为一项，保留相同变量，消去不同变量。）

next\\a，b00011110110X0001X0

next\\a，b00011110101X0000X1

然后我们根据卡诺图（这个卡诺图其实并不难看。。如果学习一下话，还是挺简单的。。）写出关系式：

a` = (a &~ next) | (b & next)

b` = (~a & ~b & next) | (b & ~next)

然后就是套公式：（Java代码，注意Go语言中是不天然支持 ~ 这种运算的）

<code> 1class Solution {
 2    public int singleNumber(int[] nums) {
 3        int a = 0, b = 0, tmp = 0;
 4        for (int next : nums) {
 5            tmp = (a & ~next) | (b & next);
 6            b = (~a & ~b & next) | (b & ~next);
 7            a = tmp;
 8        }
 9        return b;
10    }
11}/<code>

当然，其实题解还可以再近一步优化，其实就是化简上一步中的公式：

<code> 1class Solution {
 2    public int singleNumber(int[] nums) {
 3        int a = 0, b = 0;
 4        for (int next : nums) {
 5            b = (b ^ next) & ~a;
 6            a = (a ^ next) & ~b;
 7        }
 8        return b;
 9    }
10}/<code>

当然，这个解法就相当牛皮了，反正我第一次做肯定是想不到的。。。我看了一下，第一个给出这个解法的人，应该是一位国外的工程师（某扣上面有很多人其实都是把题解翻译过来的，当然我有时也会哈哈哈哈，我觉得这某种意义上讲也是一个好的现象，挺好）不过毕竟非原创，还是得说明一下！

总之，今天的题目，有一定的难度！希望大家动脑动手动脚， 认真想想。想复习一下其他位运算题目的，可以看：

閱讀更多 Java技術虎 的文章

關鍵字: 数学 出现 算法