## 一.题目描述  ## 二.解题思路 这道题与Single Number（数组中其他数出现两次，仅有一个出现一次的）有所不同，本题变为序列中有一个数出现一次，其他元素出现了三次，同样要求时间复杂度为线性，空间复杂度为常数。事实上，该算法仍可以借助位运算来实现。 首先需要确定int类型数据的长度：`intWidth = sizeof(int) * 8`，可以用`intWidth`大小的变量来存储数组中每个元素的各个二进制位上`1` 出现的次数，最后 在进行 **模3** 操作，如果为`1`，那说明这一位是要找元素二进制表示中为 `1` 的那一位。 **一个例子**： 以下有一组序列，写出每个数的二进制形式： ~~~ 13：1 1 0 1 13：1 1 0 1 13：1 1 0 1 8： 1 0 0 0 9： 1 0 0 1 9： 1 0 0 1 9： 1 0 0 1 ~~~ 统计每一位二进制位上 `1` 出现的次数，由高位到低位依次为：`7 3 0 6` ，最后对`7 3 0 6` 中各元素进行**模3(%3)**，得到：`1 0 0 0` ，即为出现一次的数的二进制表示，返回该值即可。实际上对于该命题的扩展，即：若存在一序列，除了一个数只出现一次，其他数均出现k次的情况下，同样可使用以上方法，对每一位二进制位上 `1` 出现的次数进行统计，最后进行**模k(%k)**即得到目标值。 ## 三.示例代码 ~~~ // 时间复杂度O(n)，空间复杂度O(1) class Solution { public: int findSingleNumber(int A[], int n) { const int intWidth = sizeof(int) * 8; int bitNum[intWidth] = { 0 }; // initialize int res = 0; for (int i = 0; i < intWidth; i++){ for (int j = 0; j < n; j++){ bitNum[i] += (A[j] >> i) & 1; } res |= (bitNum[i] % 3) << i; } return res; } }; ~~~ ## 四.总结 阅读了网上其他博文，发现事实上有更为高效的方法，其基本思路是利用三个变量分别保存各个二进制位上 1 出现一次、两次、三次的分布情况，最后只需返回第一个变量就行了。这种方法我本人并没有实现，日后再继续研究。