文章目录
题目描述
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
解题思路
如下图所示，考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是
3
3
3 的倍数。
因此，统计所有数字的各二进制位中
1
1
1 的出现次数，并对
3
3
3 求余，结果则为只出现一次的数字。
方法一：有限状态自动机
各二进制位的 位运算规则相同 ，因此只需考虑一位即可。如下图所示，对于所有数字中的某二进制位 1 1 1 的个数，存在 3 3 3 种状态，即对 3 3 3 余数为 0 , 1 , 2 0, 1, 2 0,1,2 。
- 若输入二进制位 1 1 1 ，则状态按照以下顺序转换；
- 若输入二进制位 0 0 0 ，则状态不变。
由于二进制只能表示 0 , 1 0, 1 0,1 ，因此需要使用两个二进制位来表示 3 3 3 个状态。设此两位分别为 t w o two two , o n e one one ，则状态转换变为：
接下来，需要通过 状态转换表 导出 状态转换的计算公式。对于任意二进制位 x x x ，有：
- 异或运算：x ^ 0 = x ， x ^ 1 = ~x
- 与运算：x & 0 = 0 ， x & 1 = x
计算
o
n
e
one
one 方法：
设当前状态为
t
w
o
two
two
o
n
e
one
one ，此时输入二进制位
n
n
n 。如下图所示，通过对状态表的情况拆分，可推出
o
n
e
one
one 的计算方法为：
if two == 0:
if n == 0:
one = one
if n == 1:
one = ~one
if two == 1:
one = 0
引入 异或运算 ，可将以上拆分简化为：
if two == 0:
one = one ^ n
if two == 1:
one = 0
引入 与运算，可继续简化为：
one = one ^ n & ~two
计算
t
w
o
two
two 方法：
由于是先计算
o
n
e
one
one ，因此应在新
o
n
e
one
one 的基础上计算
t
w
o
two
two 。
如下图所示，修改为新
o
n
e
one
one 后，得到了新的状态图。观察发现，可以使用同样的方法计算
t
w
o
two
two ，即：
two = two ^ n & ~one
返回值：
以上是对数字的二进制中 “一位” 的分析，而
i
n
t
int
int 类型的其他
31
31
31 位具有相同的运算规则，因此可将以上公式直接套用在
32
32
32 位数上。
遍历完所有数字后，各二进制位都处于状态
00
00
00 和状态
01
01
01 （取决于 “只出现一次的数字” 的各二进制位是
1
1
1 还是
0
0
0 ），而此两状态是由
o
n
e
one
one 来记录的（此两状态下
t
w
o
s
twos
twos 恒为
0
0
0 ），因此返回
o
n
e
s
ones
ones 即可。
复杂度分析：
- 时间复杂度 O ( N ) O(N) O(N) ： 其中 N N N 位数组 n u m s nums nums 的长度；遍历数组占用 O ( N ) O(N) O(N) ，每轮中的常数个位运算操作占用 O ( 32 × 3 × 2 ) = O ( 1 ) O(32 \times3 \times 2) = O(1) O(32×3×2)=O(1) 。
- 空间复杂度 O ( 1 ) O(1) O(1) ： 变量 o n e s ones ones , t w o s twos twos 使用常数大小的额外空间。
C++代码实现
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ones = 0, twos = 0;
for(int num : nums){
ones = ones ^ num & ~twos;
twos = twos ^ num & ~ones;
}
return ones;
}
};
方法二：遍历统计
注：此方法相对容易理解，但效率较低，总体推荐方法一。
使用 与运算 ，可获取二进制数字
n
u
m
num
num 的最右一位
n
1
n_1
n1：
n
1
=
n
u
m
&
i
n1=num\And i
n1=num&i配合 无符号右移操作 ，可获取
n
u
m
num
num 所有位的值（即
n
1
n_1
n1 ~
n
32
n_{32}
n32 ）：
n
u
m
=
n
u
m
>
>
>
1
num=num>>>1
num=num>>>1建立一个长度为
32
32
32 的数组
c
o
u
n
t
s
counts
counts ，通过以上方法可记录所有数字的各二进制位的
1
1
1 的出现次数。
int[] counts = new int[32];
for(int i = 0; i < nums.length; i++) {
for(int j = 0; j < 32; j++) {
counts[j] += nums[i] & 1; // 更新第 j 位
nums[i] >>>= 1; // 第 j 位 --> 第 j + 1 位
}
}
将 c o u n t s counts counts 各元素对 3 3 3 求余，则结果为 “只出现一次的数字” 的各二进制位。
for(int i = 0; i < 32; i++) {
counts[i] %= 3; // 得到 只出现一次的数字 的第 (31 - i) 位
}
利用 左移操作 和 或运算 ，可将 c o u n t s counts counts 数组中各二进位的值恢复到数字 r e s res res 上（循环区间是 i ∈ [ 0 , 31 ] i \in [0, 31] i∈[0,31] ）。
for(int i = 0; i < counts.length; i++) {
res <<= 1; // 左移 1 位
res |= counts[31 - i]; // 恢复第 i 位的值到 res
}
最终返回 r e s res res 即可。
复杂度分析
- 时间复杂度 O ( N ) O(N) O(N) ： 其中 N N N 位数组 n u m s nums nums 的长度；遍历数组占用 O ( N ) O(N) O(N) ，每轮中的常数个位运算操作占用 O ( 1 ) O(1) O(1) 。
- 空间复杂度 O ( 1 ) O(1) O(1) ： 数组 c o u n t s counts counts 长度恒为 32 32 32 ，占用常数大小的额外空间。
C++代码实现
class Solution {
public:
int singleNumber(vector<int>& nums) {
int counts[32] = {0};
for(int num : nums) {
for(int j = 0; j < 32; j++) {
counts[j] += num & 1;
num >>= 1;
}
}
int res = 0, m = 3;
for(int i = 0; i < 32; i++) {
res <<= 1;
res |= counts[31 - i] % m;
}
return res;
}
};