一种显而易见的方法就是用哈希表，但是空间复杂度为 。这里不做赘述。

对 int 整型数的每个二进制位，统计其在所有元素中出现的次数。出现次数有 3 种情况：

1. 为 0

2. 为 3 的倍数

3. 为 1

我们只需要把出现次数模 3 后为 1 的位重新组合，就得到所求数值。

为此，我们可以定义一个长度为 int 类型比特位数，也就是sizeof(int) * 8长度的 int 数组，用来统计每个二进制位出现次数。

数组长度在特定机器上是固定的，因此空间复杂度为 。C 语言实现参考上面的链接。

在上面的方法中，用一个 int 数组来统计二进制位出现次数有点浪费，事实上在统计次数时，只需要考虑 3 种情况：0、1、2，当次数到达 3 时，将其重置为 0 即可，这其实是 3 进制运算。

要保存 3 种状态，只需要 2 个比特：

int 类型的每个比特需要 2 个比特保存状态，一个保存低位比特，一个保存高位比特，那么总共只需要 2 个 int 来保存。接下来要做的就是用 2 个比特模拟 3 进制运算。

设 A 表示低位，B 表示高位，C 表示当前统计的比特，列出真值表：

先计算新的低位，逻辑表达式为

在编码实现时，计算 A’ 覆盖了原先的 A，再计算 B’ 时就需要用 A’ 计算：

用 C 语言编码为：

1
2
3
4
5

int one = 0, two = 0;
for (int i = 0; i < numsSize; ++i) {
    one = (one ^ nums[i]) & ~two;
    two = (two ^ nums[i]) & ~one;
}

最终的one恰好就是所求的数值，而two理论上为 0，因为根据题中条件不会有出现 2 次的情况。

时间复杂度为 ，空间复杂度为 ，只用了两个int。