SingleNumber问题详述

作者: M_lear | 来源:发表于2018-12-03 11:11 被阅读0次

一、认识SingleNumber问题

下面依次贴出 LeetCode 中文网上关于 SingleNumber 的三个问题，并给出问题的求解代码。

问题一、136. 只出现一次的数字（136是该题在 leetcode 中的题号，下同）

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？（之前在leetcode的评论中看到有人对这句话有疑惑，这里解释一下。他不是要求你连变量都不能声明，而是说你的算法的空间复杂度应为O(1)而不是O(n)）

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入:[4,1,2,1,2]
输出: 4

这个问题的流传度应该是最广的，我最早是在《编程之美》上看到这个问题的，当时还没听过LeetCode呢(逃)。第一次看到这个问题的时候，想这个必然需要穷举啊，每次盯住一个元素，遍历数组看这个元素有没有再次出现，时间复杂度为 $O(n^2)$ 。要不然弄一个hash表，遍历一遍也可以解决问题，但这又需要 $O(n)$ 的空间复杂度。
结果一看别人的解法，一个异或运算就可以解决问题，时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。当时那感觉(jio)，那叫一个不可思议。
下面给出这个问题的Java代码（可以直接在leetcode上提交，下同）：
解法一：

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for(int x : nums){
            res ^= x;
        }
        return res;
    }
}

解法二：

class Solution {
    public int singleNumber(int[] nums) {
        int[] s = new int[32];//位计数器
        for(int i = 0; i < nums.length; ++i){
            for(int j = 0; j < 32; ++j){
                if((nums[i] & 1<<j) != 0){//判断nums[i]的第j位是否为1
                    s[j] = (s[j]+1) % 2;
                }
            }
        }
        int res = 0;
        for(int j = 0; j < 32; ++j){
            if(s[j] > 0){
                res |= 1<<j;
            }
        }
        return res;
    }
}

本质上这两种解法是一样的，后面会进行讲解。

问题二、137. 只出现一次的数字 II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

下面给出这个问题的Java代码：
解法一：

class Solution {
    public int singleNumber(int[] nums) {
        int p = 0, q = 0;
        for(int x : nums){
            p = ~q & (p ^ x);
            q = ~p & (q ^ x);
        }
        return p;
    }
}

解法二：

class Solution {
    public int singleNumber(int[] nums) {
        int[] s = new int[32];
        for(int i = 0; i < nums.length; ++i){
            for(int j = 0; j < 32; ++j){
                if((nums[i] & 1<<j) != 0){
                    s[j] = (s[j]+1) % 3;
                }
            }
        }
        int res = 0;
        for(int j = 0; j < 32; ++j){
            if(s[j] > 0){
                res |= 1<<j;
            }
        }
        return res;
    }
}

问题三、260. 只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]

注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

下面给出这个问题的Java代码：

class Solution {
    public int[] singleNumber(int[] nums) {
        int t = 0;
        for(int e : nums) t ^= e;
        t &= -t;//保留t从右起的第一个二进制1，其余位全部置零
        int a = 0, b = 0;
        for(int e : nums){
            if((e & t) == 0) a ^= e;
            else b ^= e;
        }
        return new int[]{a, b};
    }
}

二、SingleNumber问题归纳

今天的重点是问题一和问题二，并且我们要把这类问题推广到一般形式。问题三只是问题一的扩展问题，如果彻底理解了问题一和问题二，那么问题三也将不在话下。
我在前面问题一提到过，我第一次是在《编程之美》看到问题一的。那本书对于使用异或运算解题的解释是首先异或运算的运算规则是X ^ X = 0, X ^ 0 = X，其次异或运算又满足交换律和结合律，所以所有的数异或完后就是结果。这个解释完全没问题，逻辑上也理解的通，但是当时依然在很长的一段时间里，我总感觉没有彻底理解这个问题，或者说没有理解到点子上。后来发现也确实如此。
问题一和问题二都给了两种解法，我在问题一的最后提到过，这两种解法其实是等价的。聪明的读者应该已经发现了解法二其实更直观更容易理解，理解了解法二，其实也就理解了解法一。后面我们先就解法二进行讲解，然后再讲解看起来不那么直观的解法一。

一方面，在看完问题一和问题二这两道类似的问题之后，大家有没有这样一个疑问，就是这个重复次数是任意的吗，还是其中存在什么规律。例如问题一，那个 SingleNumber 只出现 1 次，可以改为出现 4 次吗？它的出现次数依旧特殊，别的元素都出现两次，就它出现四次。答案是当然不可以，其实这个重复次数是有一定的限制的，不能是任意的。或者说如果是任意的话，那就是另一类更难解决的问题了，可能就不存在 $O(n)$ 时间复杂度， $O(1)$ 空间复杂度的解法，大家有兴趣的话，可以自己去思考一下。
下面给出SingleNumber问题的一般形式，或者说是通用问法：

给定一个非空数组，除了一个数字 $A$ 的重复次数为 $y$ ，其余数字的重复次数均为 $x( x > 1)$ 的整数倍，显然 $y$ 不是 $x$ 的整除倍，我们的目标就是找出这个数字 $A$ 。

例如对于问题一，我们可以把题目改为，除了某个元素只出现一次以外，其余元素的出现次数均为 2 的整数倍，比如出现2，4，6，8，10...次都可以，算法不变。同样的，问题二也可以改为其余元素的出现次数均为 3 的整数倍，算法不变。

另一方面，既然SingleNumber问题都与数字的重复次数有关，那么本质上SingleNumber问题就可以看作是一个计数问题，普通的求解办法是将每个数看成一个整体进行计数，此时想要在线性时间内解决问题，就必需有 $O(n)$ 的辅助空间。而存在一个很巧妙的办法是，考虑数在计算机里的二进制表示，将数分解到位，按位计数，可以将空间复杂度优化到 $O(1)$ 。

三、按位计数算法详述

现在假设有 $n$ 个数存放在 32 位的 int 型数组 $a[0\cdots n-1]$ 中，然后现在盯住 $a[i]$ 这个整数的第 $j(j\in [0,31])$ 位，记作 $a_{ij}$ 。我们将目标值 $A$ 的第 $j$ 位记作 $A_{j}$ ，将 $n$ 个数上第 $j$ 位的累加和记作 $S_{j}$ ，即 $S_{j}=\sum_{i=0}^{n-1}a_{ij}$
首先有如下事实：

若 $A_{j}=0$ ，一定有 $S_{j}=k_{1}x,k_{1}\in N^{+}$
若 $A_{j}=1$ ，一定有 $S_{j}=k_{1}x+y=k_{2}x+b,k_{2}\in N^{+}$

即 $S_j=\sum_{i=0}^{n-1}a_{ij}=\begin{cases} k_{1}x & A_{j}=0 \\ k_{2}x+b & A_{j}=1 \end{cases}$
由上式可得 $A_j=\frac{S_j\%x}{b}$
随即，便可得到目标值 $A$ $A=\sum_{j=0}^{31}A_j\cdot 2^j$

按位计数法伪码实现，即解法二

前提是需要知道数据类型的位数，下面以 32 位的 int 型为例，伪代码如下：

int singleNumber(int* a, int n){
    S[32] = {0}
    for(i = 0; i < n; ++i){
        for(j = 0; j < 32; ++j){
            if(a[i] & 1<<j){
                S[j] = (S[j]+1) % x;//对a数组第j位进行计数，x可以从题目中看出
            }
        }
    }
    A = 0;
    for(j = 0; j < 32; ++j){
        if(S[j] > 0){
            A |= 1<<j;//将A的第j位置1
        }
    }
    return A;
}

四、真值表法详述，即解法一

真值表在本题中的表现，着实让我惊艳了一下。用真值表我们可以实现我们自定义的运算规则。
在 SingleNumber 问题中，我们需要借助真值表实现一个计数器，这个计数器的功能是，每计数 $x$ 次自动清零。
如果用二进制数来当计数器，那么计数 $x$ 次，至少需要 $m$ 位二进制数。
$2^{m-1}<x\le 2^m$ 所以我们需要 $m$ 个变量（不像上一种方法，必须有 32 个变量），将 $m$ 个变量对应的第 $j$ 位逻辑上组成一个 $m$ 位的计数器，记作 $S_j$ 。计数器根据输入 $a_{ij}$ 的计数规律为： $S_j=(S_j+a_{ij})\%x$ ，即每计数 $x$ 次自动清零。计数结束后， $m$ 个变量的值要么是结果 $A$ ，要么是 0。 原理同上面描述的按位计数算法。
以重复 5 的倍数找 3 次为例，需要 3 个变量，3 个变量的对应第 $j$ 位组成一个 3 位计数器。计数器的计数过程为： $000\longrightarrow^1001\longrightarrow^1010\longrightarrow^1(011)\longrightarrow^1100\longrightarrow^1000$ 下面我们分别用 $p，q，r$ 来表示计数器的 3 个位， $input$ 相当于 $a_{ij}$ 。最后计数结束后， $p$ 位对应的变量，值为 0，而 $q，r$ 对应的变量，值为结果 $A$ 。

用真值表法求解，首先需要列出如下变量变化过程的真值表：

p	q	r	input	P	Q	R
0	0	0	0	0	0	0
0	0	1	0	0	0	1
0	1	0	0	0	1	0
0	1	1	0	0	1	1
1	0	0	0	1	0	0
0	0	0	1	0	0	1
0	0	1	1	0	1	0
0	1	0	1	0	1	1
0	1	1	1	1	0	0
1	0	0	1	0	0	0

我们根据当前的 $p,q,r$ 与输入 $input$ 经过某种关系映射后得到 $P,Q,R$ ，所以理论上因变量 $P,Q,R$ 的自变量为 $p,q,r,input$ 。
即：
$P=f(p,q,r,input)$
$Q=g(p,q,r,input)$
$R=\varphi(p,q,r,input)$
然后根据真值表，写出下列变量更新的表达式：（可不化简）
$P = p\cdot\overline{q}\cdot\overline{r}\cdot\overline{input}+\overline{p}\cdot q\cdot r\cdot input$

$Q=\overline{p}\cdot q\cdot\overline{r}\cdot\overline{input}+\overline{p}\cdot q\cdot r\cdot\overline{input}+\overline{p}\cdot\overline{q}\cdot r\cdot input+\overline{p}\cdot q\cdot\overline{r}\cdot input$
$\Rightarrow=\overline{p}\cdot q\cdot\overline{input}+\overline{p}\cdot input\cdot(q⊕r)$

$R=\overline{p}\cdot\overline{q}\cdot r\cdot\overline{input}+\overline{p}\cdot q\cdot r\cdot\overline{input}+\overline{p}\cdot\overline{q}\cdot\overline{r}\cdot input+\overline{p}\cdot q\cdot\overline{r}\cdot input$
$\Rightarrow=\overline{p}\cdot r\cdot\overline{input}+\overline{p}\cdot\overline{r}\cdot input$
$\Rightarrow=\overline{p}\cdot(r⊕input)$

以上是一位的计数运算，而实际上对于位运算来说所有位的运算都是相同的。故而上述算法不用分解到位，单独运算，再进行整合。对于上面的式子，如果你忘记了怎么化简，不化简也可以，不影响大局。

真值表法实现自动计数，不仅可以进一步优化空间复杂度，而且不需要知道具体的数据类型位数。重复 5 的倍数找 3 次的 SingleNumber 问题的真值表法C语言代码如下：

#include<stdio.h>
int singleNumber(int* a, int len){
    int p = 0, q = 0, r = 0;
    int op;
    for(int i = 0; i < len; i++){
        op = p;//临时变量保存p的值。因为下面p要先更新，而后面q，r的更新又需要用到p的旧值
        p = (p & ~q & ~r & ~a[i])|(~p & q & r & a[i]);
        q = (~op & q & ~a[i])|(~op & a[i] & (q^r));
        r = ~op & (r^a[i]);//这里r的更新没有用到q，否则还需要一个临时变量保存q的旧值
    }
    return r;
}
int main(){
    int a[13] = {5,5,5,2,2,7,7,7,7,7,2,5,5};
    printf("%d\n",singleNumber(a,13));
    return 0;
}

到了这里还没完哦，其实我们可以进一步优化空间复杂度，去掉在更新过程中用到的临时变量。例如问题二的解法一就没有临时变量。那我们应该怎么做呢？
答案是，换一下映射关系中的自变量即可，使用最新的值去更新后面的变量。
映射关系如下所示：
$P=f^{'}(p,Q,R,input)$
$Q=g^{'}(P,q,R,input)$
$R=\varphi^{'}(P,Q,r,input)$
根据真值表，可以写出如下新的变量更新表达式：
$P = p\cdot\overline{Q}\cdot\overline{R}\cdot\overline{input}+\overline{p}\cdot\overline{Q}\cdot\overline{R}\cdot input=\overline{Q}\cdot\overline{R}\cdot(p⊕input)$

$Q=\overline{P}\cdot q\cdot\overline{R}\cdot\overline{input}+\overline{P}\cdot q\cdot R\cdot\overline{input}+\overline{P}\cdot\overline{q}\cdot\overline{R}\cdot input+\overline{P}\cdot q\cdot R\cdot input$
$\Rightarrow=\overline{P}\cdot input\cdot(\overline{q}\cdot\overline{R}+q\cdot R)+\overline{P}\cdot q\cdot\overline{input}$

$R=\overline{P}\cdot\overline{Q}\cdot r\cdot\overline{input}+\overline{P}\cdot Q\cdot r\cdot\overline{input}+\overline{P}\cdot\overline{Q}\cdot\overline{r}\cdot input+\overline{P}\cdot Q\cdot\overline{r}\cdot input$
$\Rightarrow=\overline{P}\cdot(r⊕input)$
C语言代码如下：

#include<stdio.h>
int singleNumber(int* a, int len){
    int p = 0, q = 0, r = 0;
    for(int i = 0; i < len; i++){
        p = ~q & ~r & (p^a[i]);
        q = ~p & a[i] & (~q & ~r|q & r)|~p & q & ~a[i];
        r = ~p & (r^a[i]);
    }
    return q;//只能返回q。p和r为0，为什么？
}
int main(){
    int a[13] = {5,5,5,2,2,7,7,7,7,7,2,5,5};
    printf("%d\n",singleNumber(a,13));
    return 0;
}

留一个问题给大家自己思考，为什么优化后的代码只能返回 $q$ ，而之前的代码却返回 $q，r$ 都可以呢。

五、最后提一下问题三

假设那两个只出现一次的元素分别为 $A$ 和 $B$ ，由题意易知 $A\ne B$ 。

将所有元素依次做一遍异或运算，则最终的结果就是 $A⊕B$ 。由于 $A\ne B$ ，故 $A⊕B\ne0$ 。
则必然存在这种情况， $A$ 和 $B$ 在某一位上必然一个为 1，一个为 0。而这一位可以根据 $A⊕B$ 上的非零位确定。
根据所有元素在这一位上是 0 还是 1，可以将元素分为两类。由于 $A$ 和 $B$ 必然不可能出现在同一类中，所以这两类元素就等价于两个问题一。将这两类元素分别各自做异或运算，就可以分别得到 $A$ 和 $B$ 。

最后的最后再给大家一个扩展问题自己思考并动手编码，其实如果上面的内容都懂了的话，这个题应该很简单。问题如下：

给定一个整数数组 nums，其中恰好有两个元素分别只出现了一次和两次，其余所有元素均出现三次。找出只出现一次和只出现两次的那两个元素。

SingleNumber问题详述

一、认识SingleNumber问题

问题一、136. 只出现一次的数字（136是该题在 leetcode 中的题号，下同）

问题二、137. 只出现一次的数字 II

问题三、260. 只出现一次的数字 III

二、SingleNumber问题归纳

三、按位计数算法详述

按位计数法伪码实现，即解法二

四、真值表法详述，即解法一

五、最后提一下问题三

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

p	q	r	input	P	Q	R
0	0	0	0	0	0	0
0	0	1	0	0	0	1
0	1	0	0	0	1	0
0	1	1	0	0	1	1
1	0	0	0	1	0	0
0	0	0	1	0	0	1
0	0	1	1	0	1	0
0	1	0	1	0	1	1
0	1	1	1	1	0	0
1	0	0	1	0	0	0

p	q	r	input	P	Q	R
0	0	0	0	0	0	0
0	0	1	0	0	0	1
0	1	0	0	0	1	0
0	1	1	0	0	1	1
1	0	0	0	1	0	0
0	0	0	1	0	0	1
0	0	1	1	0	1	0
0	1	0	1	0	1	1
0	1	1	1	1	0	0
1	0	0	1	0	0	0

p	q	r	input	P	Q	R
0	0	0	0	0	0	0
0	0	1	0	0	0	1
0	1	0	0	0	1	0
0	1	1	0	0	1	1
1	0	0	0	1	0	0
0	0	0	1	0	0	1
0	0	1	1	0	1	0
0	1	0	1	0	1	1
0	1	1	1	1	0	0
1	0	0	1	0	0	0