「LeetCode」只出现一次的数字 I, II, III

2020-04-07
摘要: 本文总结了 LeetCode 上的经典问题:只出现一次的数字 I, II, III

只出现一次的数字 I#

https://leetcode-cn.com/problems/single-number/

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

异或的概念

一个数与 $0$ 进行 XOR 还是自身:$a\oplus 0 = 0$

一个数与自身 XOR 为 $0$:$a\oplus a = a$

XOR 满足交换律与结合律:$a \oplus b \oplus a=(a \oplus a) \oplus b=0 \oplus b=b$

所以我们只需要将所有的数进行 XOR 操作,得到那个唯一的数字。

因为所有重复的数字 XOR 结果都为 $0$,而 $0$ 与剩下的数字 XOR 是其本身。时间复杂度为 $O(n)$,空间复杂度为 $O(1)$。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(auto num : nums) {
            res ^= num;
        }
        return res;
    }
};

只出现一次的数字 II#

https://leetcode-cn.com/problems/single-number-ii/

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

如果按照同样的思路进行 XOR,那么我们得到的数字便是所有数字的 XOR 值,因为 $a \oplus a \oplus a = a$。于是需要想办法把出现一次和出现三次的数字分开。直观的思路是,统计每一位上 $1$ 出现的次数,它们必然为 $3k$ 或者 $3k+1$。所有 $3k+1$ 的位组合在一起便是我们需要找的数 $x$。

另外,如果我们利用自动机来判断每一位的状态:

当然可以合并 $S_0$ 和 $S_3$:

实际上,出现 $3$ 次和出现 $0$ 次是一样的。因为一共有三个状态,所以我们最少需要用两个变量。我们用 `once` 代表 $S_1$,`twice` 代表 $S_2$。于是:

$$
\begin{array}{|l|c|c|c|}
\hline (\mathrm{once},\mathrm{twice})& (0,0) & (0,1) & (1,0) \
\hline x=0 & (0,0) & (0,1) & (1,0) \
\hline x=1 & (1,0) & (0,0) & (0,1) \
\hline\end{array}
$$

我们只需要找到 once 最后代表的数字($1$ 出现次数为 $3k+1$ 次的位最终值为 $1$),即为 $x$。

转移方程如下:

观察表格,once 只能在 $S_0(x=1),S_1(x=0)$ 之后为 $1$: once = (once & ~x) | (~once & ~twice & x)

twice 只能在 $S_1(x=1),S_2(x=0)$ 之后为 $1$: twice = (once & x) | (twice & ~x)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int once = 0, twice = 0;
        for(auto x : nums) {
            int _once = once;
            once = (once & ~x) | (~once & ~twice & x);
            twice = (_once & x) | ( twice & ~x);
        }
        return once;
    }
};

只出现一次的数字 III#

https://leetcode-cn.com/problems/single-number-iii/

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

如果按照同样的思路进行 XOR,那么我们得到的数字便是两个数字 $x,y$ 的 XOR 值。思考一下这个数字代表了什么?不难发现,$x \oplus y$ 中为 $1$ 的位意味着它们在 $x,y$ 对应的位中有不同的值。

然后我们应该思考如何才能将 $x,y$ 从 $x \oplus y$ 中分离。其实,我们做不到,因为我们只能找到它们的差异位。

我们换一个思路,考虑将 $x,y$ 从这一组数中分开。什么意思呢?我们随便找一个差异位,比如第 $i$ 位,记 $x$ 的第 $i$ 位为 $1$, 那么 $y$ 的第 $i$ 位就是 $0$。此时我们再遍历整个数组,只有当 $nums[\mathrm{index}]$ 的第 $i$ 位为 $1$ 时,我们才与它进行 XOR 运算。这样下来,我们只计算了所有第 $i$ 位为 $1$ 的数,而 $y$ 不在其中,所以结果就是 $x$。同理,我们可以得到 $y$,不过直接可以借助 $x \oplus y \oplus x$ 来得到 $y$。

怎么随便找一个差异位呢?只要在 $x \oplus y$ 中随便取一个结果为 $1$ 的位就行。不过,对于任意二进制数 $x$ 来说,x & -x 的结果就是保留最后一个 $1$,其他都置 $0$,这样可以快速地得到一个差异位。

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int firstRes = 0;
        for(auto num : nums) {
            firstRes ^= num;
        }

        int diff = firstRes & -firstRes;
        
        int secondRes = 0;
        for(auto num : nums) {
            if(num & diff) secondRes ^= num;
        }

        return vector<int>{secondRes, firstRes^secondRes};
    }
};