Source
Given 3*n + 1 numbers, every numbers occurs triple times except one, find it. Example Given [1,1,2,3,3,3,2,2,4,1] return 4 Challenge One-pass, constant exstra space
题解 – 逐位处理
之前 Single Number 用到了二进制中异或的运算特性，这题给出的元素数目为3*n + 1，因此我们很自然地想到如果有种运算能满足「三三运算」为0该有多好！对于三个相同的数来说，其相加的和必然是3的倍数，仅仅使用这一个特性还不足以将单数找出来，我们再来挖掘隐含的信息。以3为例，若使用不进位加法，三个3相加的结果为：
0011 0011 0011 ---- 0033
注意到其中的奥义了么？三个相同的数相加，不仅其和能被3整除，其二进制位上的每一位也能被3整除！因此我们只需要一个和int类型相同大小的数组记录每一位累加的结果即可。时间复杂度约为 O((3n+1)⋅sizeof(int)⋅8)
C++ bit by bit
class Solution { public: /** * @param A : An integer array * @return : An integer */ int singleNumberII(vector<int> &A) { if (A.empty()) { return 0; } int result = 0, bit_i_sum = 0; for (int i = 0; i != 8 * sizeof(int); ++i) { bit_i_sum = 0; for (int j = 0; j != A.size(); ++j) { // get the *i*th bit of A bit_i_sum += ((A[j] >> i) & 1); } // set the *i*th bit of result result |= ((bit_i_sum % 3) << i); } return result; } };
源码解析
- 异常处理
- 循环处理返回结果
result的int类型的每一位，要么自增1，要么保持原值。注意i最大可取 8⋅sizeof(int)−1, 字节数=>位数的转换 - 对第
i位处理完的结果模3后更新result的第i位，由于result初始化为0，故使用或操作即可完成
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/20648.html