【4.30】LeetCode每日一题· 只出现一次的数字 II

2021年04月30日 10时10分

标签： LeetCode 二进制哈希表

## 题目描述

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

#### 示例1

```
输入：nums = [2,2,3,2]
输出：3
```

#### 示例2

```
输入：nums = [0,1,0,1,0,1,99]
输出：99
```

#### 提示

```
1 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
```

#### 来源

> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/single-number-ii "题目链接")

## 解题思路

### 哈希表+计数

最简单的思路，维护一个哈希表记录`nums`中每个数字出现的次数，最后遍历哈希表，将出现次数为1的数字返回即可。

时间复杂度：$$O(n)$$；
空间复杂度：$$O(n)$$

#### 代码

```cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for(int& num: nums){
            cnt[num]++;
        }
        for(auto& item: cnt){
            if(item.second == 1){
                return item.first;
            }
        }
        return -1;
    }
};
```

#### 用时和内存

> 执行用时：4 ms，在所有 C++提交中击败了96.94%的用户
> 内存消耗：9.7 MB，在所有 C++提交中击败了15.34%的用户

### 位运算

注意到题目中一个特别奇怪的条件：除了某个元素以外，其他元素都**出现3次**。

考虑一个更为简单的情况：如果其他每个元素都**出现两次**，那么将所有数**取亦或**，则出现两次的数的对应二进制位都会被抵消，只会留下唯一的出现一次的数。

那么现在其他元素都**出现3次**怎么处理呢？借鉴**出现2次**的做法，把`nums`中所有数字的二进制位相加，那么**出现3次**的数对**每个二进制位的贡献都是3的倍数（对于某个数的某一二进制位，如果为1，那么贡献为3；如果为0，那么贡献为0）**，而**出现1次**的数对**每个二进制位的贡献都是1或0（如果某一二进制位为1，则贡献为1；如果为0，则贡献为0）**，因此如果我们把求和之后的二进制位都**对3取余数**，就会把**所有出现3次的数的二进制位抵消**，剩下的数就是答案。

由于每个二进制位只能存储`0, 1`两种状态，而在对每个二进制位进行求和的时候，可能会出现`0, 1, 2`三种状态；所以只能新创建一个**cnt**变量，对所有数的每一个二进制位分别进行遍历求和，并计算答案的对应二进制位。

时间复杂度：$$O(n\log C)$$（$$C$$为数组的二进制位数）；
空间复杂度：$$O(1)$$

#### 代码

```cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < 32; i++){
            int cnt = 0;
            for(int& num: nums){
                if((num >> i)&1){
                    cnt++;
                }
            }
            res |= ((cnt%3) << i);
        }
        return res;
    }
};
```

#### 用时和内存

> 执行用时：4 ms，在所有 C++提交中击败了96.94%的用户
> 内存消耗：9.3 MB，在所有 C++提交中击败了27.37%的用户

### 位运算逻辑优化

再回到其他每个元素都**出现两次**的情况，我们之所以可以将所有数**取亦或**得到答案的原因是，对所有数的二进制位相加时，只会出现`0, 1`两种情况，使用`1`个二进制位即可表示这两种状态，并且利用**异或**的性质，模拟了**对2取余**的运算。

而当其他元素**出现3次**时，由于对二进制位相加的时候，会出现`0, 1, 2`三种情况，无法使用一个二进制位表示，导致了我们的算法必须对每一二进制位分别计数（而无法直接对整个数字的所有二进制位进行批处理），致使时间复杂度里产生了$$\\log C$$这一项。

再回到，那么我们有没有办法设计出一个**逻辑电路**，或者位运算逻辑，将其**对标每个元素都出现两次时的抑或运算**呢？我们可以使用两个变量`a, b`，根据`a, b`元素每个二进制位的状态组合表示出`3`种状态：

```
[a, b] = [0, 0]表示数字1
[a, b] = [0, 1]表示数字2
[a, b] = [1, 0]表示数字3
```

同时可以使用`[0, 0] -> [0, 1] -> [1, 0] -> [0, 0]`表示遍历所有数字的二进制位为1时的状态转移。

当遍历到一个整数$$x$$时，其第$$i$$个二进制位为$$x\_i$$，那么可以得到如下的状态转移真值表：

| [$$a_i$$, $$b_i$$] | $$x_i$$ | [新的$$a^\prime_i$$, $$b^\prime_i$$] |
| ------------------ | ------- | ------------------------------------ |
| [0, 0]             | 0       | [0, 0]                               |
| [0, 0]             | 1       | [0, 1]                               |
| [0, 1]             | 0       | [0, 1]                               |
| [0, 1]             | 1       | [1, 0]                               |
| [1, 0]             | 0       | [1, 0]                               |
| [1, 0]             | 1       | [0, 0]                               |

根据卡诺图画出真值表，可以得到如下的状态转移位运算逻辑：

```math
\displaystyle
a^\prime = x\bar{a}b + \bar{x}a\bar{b} 
```
```math
\displaystyle
b^\prime = x\bar{a} \bar{b} + \bar{x}\bar{a}b = \bar{a}(x\oplus b)
```
这样就可以对每一个数字的所有二进制位进行批处理了。

时间复杂度：$$O(n)$$；
空间复杂度：$$O(1)$$

#### 代码

```cpp
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0, ta, tb;
        for(int& num: nums){
            ta = (num&(~a)&b) | ((~num)&a&(~b));
            tb = (~a)&(num^b);
            a = ta;
            b = tb;
        }
        return b;
    }
};
```

#### 用时和内存

> 执行用时：4 ms，在所有 C++提交中击败了96.94%的用户
> 内存消耗：9.3 MB，在所有 C++提交中击败了22.03%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.30】LeetCode每日一题· 只出现一次的数字 II

所有评论

暂无评论

新增评论