题目:
Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

思路:
一个比较好的方法是从位运算来考虑。每一位是0或1,由于除了一个数其他数都出现三次,我们可以检测出每一位出现三次的位运算结果再加上最后一位即可。

class Solution {
public:
int singleNumber(int A[], int n) {
int ones = , twos = , threes = ;
for(int i = ; i < n; i++)
{
threes = twos & A[i]; //已经出现两次并且再次出现
twos = twos | ones & A[i]; //曾经出现两次的或者曾经出现一次但是再次出现的
ones = ones | A[i]; //出现一次的 twos = twos & ~threes; //当某一位出现三次后,我们就从出现两次中消除该位
ones = ones & ~threes; //当某一位出现三次后,我们就从出现一次中消除该位
}
return ones; //twos, threes最终都为0.ones是只出现一次的数
}
};
04-24 12:54