思路
思路一
时间复杂度 $O(nlogn)$,空间复杂度 $O(1)$。
若能确定结果的哪些二进制位为 $1$ 就能确定答案。不考虑结果时,数组中其它所有数第 $i$ 位是 $1$ 的个数是 $3k, k \in N$,若结果的第 $i$ 位是 $1$,数组中第 $i$ 位是 $1$ 的数的个数等于 $3k + 1$,否则等于 $3k$。
因此可逐位统计每一位 $1$ 的个数,当个数除 $3$ 余 $1$ 时,将结果的当前位置 $1$。
思路二
时间复杂度 $O(n)$,空间复杂度 $O(1)$。
数字电路设计。准备一个黑盒,它的第 $i$ 位存储着扫描过的所有数第 $i$ 位之和除以 $3$ 的余数。由于余数可能为 $0, 1, 2$,因此需要两个二进制位存储它,记为 $a_i, b_i$。记当前数的第 $i$ 位为 $x_i$,则有以下真值表:
$(a_i, b_i)$ | $x_i$ | 新 $(a_i, b_i)$ |
---|---|---|
00 | 0 | 00 |
00 | 1 | 01 |
01 | 0 | 01 |
01 | 1 | 10 |
10 | 0 | 10 |
10 | 1 | 00 |
从上表可观察出,若第 $i$ 位 $1$ 的个数为 $3k + 1$,则 $b_i = 1$,否则 $b_i = 0$,因此最终 $b$ 的所有位就是答案。
由于一位的状态需要两个二进制位,实现时用两个整数比较方便。因此需要把 $a_i$ 和 $b_i$ 的真值表拆开。
$(a_i, b_i)$ | $x_i$ | 新 $a_i$ |
---|---|---|
00 | 0 | 0 |
00 | 1 | 0 |
01 | 0 | 0 |
01 | 1 | 1 |
10 | 0 | 1 |
10 | 1 | 0 |
$(a_i, b_i)$ | $x_i$ | 新 $b_i$ |
---|---|---|
00 | 0 | 0 |
00 | 1 | 1 |
01 | 0 | 1 |
01 | 1 | 0 |
10 | 0 | 0 |
10 | 1 | 0 |
可据此写出布尔表达式
$$ \begin{aligned} a_i &= a_{i}^{\prime}b_ix_i + a_{i}b_{i}^{\prime}x_{i}^{\prime} \\\ b_i &= a_{i}^{\prime}b_{i}^{\prime}x_i + a_{i}^{\prime}b_{i}x_{i}^{\prime} \\\ &= a_{i}^{\prime}(b_i \oplus x_i) \end{aligned} $$
由于 $a_i$ 的转换比较复杂,而 $b_i$ 比较简单,尝试用新 $b_i$ 推 $a_i$。
$(a_i, \mathbf{新} b_i)$ | $x_i$ | 新 $a_i$ |
---|---|---|
00 | 0 | 0 |
01 | 1 | 0 |
01 | 0 | 0 |
00 | 1 | 1 |
10 | 0 | 1 |
10 | 1 | 0 |
$$ \begin{aligned} a_i &= a_{i}^{\prime}b_{i}^{\prime}x_i + a_{i}b_{i}^{\prime}x_{i}^{\prime} \\\ &= b_{i}^{\prime}(a_i \oplus x_i) \end{aligned} $$
CPP
// 思路一
class Solution {
public:
int findNumberAppearingOnce(vector<int>& nums) {
int x = 0;
for (int i = 0; i < 32; i++) {
int ones = 0;
for (unsigned u: nums)
ones += u >> i & 1;
x |= (ones % 3) << i;
}
return x;
}
};
// 思路二
class Solution {
public:
int findNumberAppearingOnce(vector<int>& nums) {
int a = 0, b = 0;
for (auto x: nums)
tie(a, b) = pair {
~a & b & x | a & ~b & ~x,
~a & (b ^ x)
};
return b;
}
};
// 思路二化简
class Solution {
public:
int findNumberAppearingOnce(vector<int>& nums) {
int a = 0, b = 0;
for (auto x: nums) {
b = ~a & (b ^ x);
a = ~b & (a ^ x);
}
return b;
}
};
JAVA
// 思路二
class Solution {
public int findNumberAppearingOnce(int[] nums) {
int a = 0, b = 0;
for (var x: nums) {
b = ~a & (b ^ x);
a = ~b & (a ^ x);
}
return b;
}
}