[OJ] Single Number II

LintCode 83. Single Number II (Medium)

LeetCode 137. Single Number II (Medium)

以下算法的复杂度都是:

时间复杂度: O(n)

空间复杂度: O(1)

解法1. 32个计数器

最简单的思路是用32个计数器, 满3复位0.

class Solution {
public:
int singleNumberII(vector<int> &A) {
int cnt[32] = {0};
int res = 0;
for (int i = 0; i < 32; ++i) {
for (int n : A) {
cnt[i] += (n >> i) & 1;
cnt[i] %= 3;
}
res |= cnt[i] << i;
}
return res;
}
};

解法2. 找规律

我的思路是, 解法1中的计数其实只需要两个bit就够了. 所有的首个bit记做res, 所有的第二个bit记做carry, 找规律:

如果A[i]的第k位是0, 则rescarry的第k位保持原样.

如果A[i]的第k位是1, 则:

res carry res' carry'
0 0 1 0
1 0 0 1
0 1 0 0

此时(A[i][k]=1时)的规律就是:

res'[k]=~res[k] & ~carry[k]

carry'[k]=res[k] & ~carry[k]

class Solution {
public:
int singleNumberII(vector<int> &A) {
int res = 0, carry = 0;
for (int n : A) {
for (int i = 0; i < 32; ++i) {
int mask = (1 << i);
int bit = n & mask;
if (bit) {
int newRes = (~mask & res) + ((~res & mask) & (~carry & mask));
carry = (~mask & carry) + ((res & mask) & (~carry & mask));
res = newRes;
}
}
}
return res;
}
};

解法2.1. 解法2的简化

解法2中, 将A[i][k]=0=1的情况合并, 可以得到:

res'[k]=(A[i][k] & ~res[k] & ~carry[k]) | (~A[i][k] & res[k])

carry'[k]=(A[i][k] & res[k] & ~carry[k]) | (~A[i][k] & carry[k])

这样的好处是可以32位一起算, 而不用一位一位地算:

res'=(A[i] & ~res & ~carry) | (~A[i][k] & res)

carry'=(A[i] & res & ~carry) | (~A[i][k] & carry)

class Solution {
public:
int singleNumberII(vector<int> &A) {
int res = 0, carry = 0;
for (int n : A) {
int newRes = (n & (~res & ~carry)) | (~n & res);
carry = (n & (res & ~carry)) | (~n & carry);
res = newRes;
}
return res;
}
};

解法3. one, two, three

Discuss中看到的解法, 自己实在想不出来. 用one, twothree三个int值作为bit flags.

循环对A[0]A[n]进行考察, 当考察A[i]时:

S[i]={A[0],...,A[i]},

S[i]中所有数字的第k位bit的数目%3==1, 则one的第k位为1, 否则为0.

S[i]中所有数字的第k位bit的数目%3==2, 则two的第k位为1, 否则为0.

three是一个临时变量, 用于记录这一轮中, 哪些bit的数目恰巧是3的倍数.

two |= one & n;: 给two加上那些从1到2的数字.

one ^= n;: 这句比较巧妙, 既删掉了会变成2的那些1, 又加上了新的1.

three = one & two;: 1+2=3...

one&= ~three: 从1中刨去那些成为3的1.

two&= ~three: 从2中跑去那些成为3的2.

...如果你能解释得更清晰易懂, 欢迎留言!

class Solution {
public:
int singleNumberII(vector<int> &A) {
int one = 0, two = 0, three = 0;
for (int n : A) {
two |= one & n;
one ^= n;
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
};

解法3.1. 解法3的变形

自己没想出解法4, 但是参照它的思路, 写了一个对自己比较直观的算法.

three = two & n;: 算出从2变成3的那些2.

two = (two & ~three) | (one & n);: (two & ~three)是从2中刨去那些变为3的2, (one & n)是加上那些从1变成2的1.

one = (one & ~n) | (n & ~three & ~two);: (one & ~n)是从1中刨去那些变成2的1, (n & ~three & ~two)是加上那些没给"2变3"或"1变2"用过的1.

class Solution {
public:
int singleNumberII(vector<int> &A) {
int one = 0, two = 0;
for (int n : A) {
int three = two & n;
two = (two & ~three) | (one & n);
one = (one & ~n) | (n & ~three & ~two);
}
return one;
}
};
上一篇:(转)关于C++ const 的全面总结


下一篇:【leetcode】Single Number && Single Number II(ORZ 位运算)