刷题笔记(4):力扣-137.只出现一次的数字 II

本题来自 leetcode 题库第 137 题:137.只出现一次的数字 II。题目要求找到数组中只出现过一次的数字(其他数字恰好出现 3 次),该题比较巧妙的解法涉及自动机、位运算和电路设计等知识,很有意思。难度中等。

题目描述

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

  • 示例 1:
    输入:nums = [2,2,3,2]
    输出:3

  • 示例 2:
    输入:nums = [0,1,0,1,0,1,99]
    输出:99

  • 提示:

    • \(1 \leqslant \text{nums.length} \leqslant 3 \times 10^4\)
    • \(-2^{31} \leqslant \text{nums[i]} \leqslant 2^{31} - 1\)
    • nums 中,除某个元素仅出现一次外,其余每个元素都恰出现三次

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

题解

解法1 哈希表

这道题目最直接的思路就是使用哈希表统计每个元素出现的次数,统计完毕后遍历哈希表找到只出现一次的元素即可。代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function (nums) {
const freq = new Map()
for (const num of nums) {
count = freq.get(num)
if (count) freq.set(num, ++count)
else freq.set(num, 1)
}
for (const [k, v] of freq) {
if (v === 1) return k
}
}

该方法时间复杂度为 \(O(n)\),空间复杂度为 \(O(n)\)。我个人觉得是个不错的方法,简单高效,并且可以查找出现任意次数的所有元素。

解法2 依次确定每一个二进制位

该方法利用题目的特殊点——除目标元素出现一次外其余元素均恰好出现三次。若将数组内所有数字的每个数位都单独求和,由于只有一个数字出现一次,其余数字恰出现 3 次。那么这些恰出现 3 次的数字每个数位的和都是 3 的倍数,再加上我们要找的只出现一次的数字,那么每个数位上的和对 3 取余,即为要寻找数字在该数位上的值。例如,有输入 [8,8,8,12],我们单独每个数位求和得到个位数上和为 \(8+8+8+2=26\),十位数上为 \(1\),对 \(26\)\(1\) 分别对 \(3\) 取余,得到 \(2\)\(1\),那么便有 \(12\) 是我们要寻找的只出现一次的数字。

这个思路非常巧妙,但处理起来有一些细节比较麻烦。比如确定数字有多少位,如何遍历每个数字的每一位。这些问题在二进制下使用位运算可以很好的解决。首先确定了数值范围为 32 位整型。将数组里每个数字的二进制位的各个数位求和。由于二进制每个数位只能是 10,那么对 3 取余后的值也只会是 10。得到这些数字后,再按照他们所处的数位拼合成最后的结果就可以了。具体的代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function (nums) {
let ans = 0
for (let i = 0; i < 32; i++) {
let sum = 0
for (let num of nums) {
sum += ((num >> i) & 1)
}
ans |= ((sum % 3) << i)
}
return ans
};

该算法的时间复杂度为 \(O(n\log C)\),本题中 \(\log C = 32\),一般情况下可认为是 \(O(n)\)。空间复杂度为 \(O(1)\)

注意,代码里用到了很多二进制位运算的处理。例如 (num >> i) & 1 便是求 num 二进制下第 i 位上的数字。并且注意到第 12 行在求 ans 时使用了 |= 运算符,在这里使用 += 也可以。但要注意,这两种运算是不同的,这里之所以能够互换是因为 |= 后的数值 ((sum % 3) << i) 最多只在某一位上有 1,其余位均为 0。否则两者运算不可互换,例如 11 | 10 == 1111 + 10 == 101

解法3 有限状态自动机

如果说解法 2 巧妙利用了算术知识,那么解法 3 则在此基础上运用了编译原理中有关自动机的知识,进一步降低了算法复杂度。对于该解法,之前没有接触过相关知识的话我觉得短时间内不太可能自己想出来。

对于解法 2 中计算每个数位的和时,我们考虑每一次叠加时数位和对 3 取余的值,可能的结果只有 \(0,1,2\)。由于二进制每个数位上只可能是 \(0\)\(1\)。所以,若下一个加数为 \(0\),则取余的结果维持不变;若下一个加数为 \(1\) 则取余的结果会由 \(0\) 变成 \(1\)\(1\) 变成 \(2\),或 \(2\) 变成 \(0\),即发生状态的转移。为了引入位运算,我们使用两个二进制位来记录这个状态变化,则得到以下状态变化的规律:

a b n -> a b
0 0 0 0 0
0 1 0 0 1
1 0 0 1 0
0 0 1 0 1
0 1 1 1 0
1 0 1 0 0

其中 a 和 b 分别表示余数的第 2 位和第 1 位上的值, n 表示加数。例如余数为 2 时,则 a=1,b=0。使用状态转移图表示更加直观:

图 1 状态转移图

根据以上转移规律,我们可以根据当前的 a 和 b 以及当前的加数 n 计算出下一个状态的 a 和 b(方便起见,记作 a' b')。所有的转移规律都在上表中了。但如果我们能找到更简洁的规律就更好了。

我们先求 b。首先我们发现当 a=1 时,b'=0 ;当 a=0 时,若 n=0 则 b'=b,若 n=1 则 b'=~b。即

1
2
3
4
5
6
7
if a == 1:
b = 0
if a == 0:
if n == 0:
b = b
if n == 1:
b = ~b

引入异或 ^ 运算后化简为

1
2
3
4
if a == 1:
b = 0
if a == 0:
b = b ^ n

进一步可化简为 b = ~a & (b ^ n)。由此我们获得了更新 b 的式子,使用更新后的 b 同理可发现更新 a 的规律。实际上,我们将状态转移图中的 b 替换为下一状态的 b,并颠倒 a b 的位置,会发现状态转移图是等价的。具体见下图:

图 2 更新b后的状态转移图

上图将原状态图的 b 值更新,然后颠倒 a b 的位置:

图 3 颠倒 a b 的位置

可以发现上图和原状态转移图 1 是等价的。因此立马得到 a = ~b & (a ^ n),其中 b 是更新后的 b

如此一来,对于每个数位上代表余数的 a b 两个值,每当一个新的加数 n 加入时,就有如下的变化规律:

1
2
b = ~a & (b ^ n)
a = ~b & (a ^ n)

当所有加数遍历完毕,便可以根据 ab 的值来确定该数位上待求的具体值。由于位运算是可以并行的,所以不需要对每个数位都进行遍历,由此降低了时间复杂度。具体的代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function (nums) {
let a = 0
let b = 0
for (let n of nums) {
b = ~a & (b ^ n)
a = ~b & (a ^ n)
}
return b
}

注意,由于最后每个数位上的值只可能是 10,也就是说 a 一定为 0,所以只返回 b 即可。

该算法时间复杂度为 \(O(n)\),空间复杂度为 \(O(1)\)

总结与思考

这道题并不算难,难点在于设计出空间复杂度为 \(O(1)\) 的算法。尤其看到如此简洁的解法 3 时,我深受震撼,发觉自己知识的浅薄。但实际业务场景中,我觉得解法 1 应该是更好的算法,因为后面两种算法的应用场景限制更多,只能查找唯一出现的那一个数,并且代码难以阅读。但做题的目的不是为了解决题目本身,而是从中积累和学习思路方法。尤其后面解法中涉及的自动机和位运算的知识和技巧,需要学习和积累。