LeetCode 137 Single Number II

Posted on | In | 阅读
  1. 这题比起其他都是两个但有一个只出现一次要复杂一些，原来只需要统计（模2）出现0次，1次的情况，现在需要统计每一位出现了0次，1次和2次（模3）的状态。
  2. 用one two three来统计每一位出现次数，出现在three中的可以从one two中约去
  3. 每一个数，首先和one与一下，得到原来是1次，现在变成两次的情况，或到two中
  4. 再和one抑或，原来是0的变成1，原来是1的由于进入two了变成0
  5. one和two与，得到出现三次的情况，把他们从one two中抑或掉或者与非掉就行
  6. 最后的one就是最后的结果（模3为1）

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0, three = 0;
        for(int i = 0; i < nums.size(); i++){
            two |= (one & nums[i]);
            one ^= nums[i];
            three = (two & one);
            one ^= three;
            two ^= three;
        }
        return one;
    }
};