经典题。数电设计+位运算。具体分析太多太复杂了,实在懒得写……仅把优美的方法记下来并加一点理解。
1. x1, x2, ... ... , xm作为标记位, mask通过k的二级制表达确定,本题为~(x1 & x2)
int singleNumber(vector<int>& nums) {
int x1 = 0, x2 = 0, mask = 0;
for (int i : nums) {
x2 ^= x1 & i;
x1 ^= i;
mask = ~(x1 & x2);
x2 &= mask;
x1 &= mask;
}
return x1;
}
2. 00->01->10->00 ones记录刚好出现一次的,twos记录刚好出现两次的。
int singleNumber(vector<int>& nums) {
int ones = 0, twos = 0;
for(int i : nums){
ones = (ones ^ i) & (~twos);
twos = (twos ^ i) & (~ones);
}
return ones;
}
3. 输入输出table设计
# ab c/c ab/ab
//# 00 1/0 01/00
//# 01 1/0 10/01
//# 10 1/0 00/10
int singleNumber(vector<int>& nums) {
int a = 0,b = 0;
for (int c : nums){
int ta = (~a&b&c) | (a&~b&~c);
b = (~a&~b&c) | (~a&b&~c);
a=ta;
}
return a|b;
}