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?

通用做法，统计每一位当中，1出现的次数.

在统计了所有数各个位置上1的出现次数之后, 如果一个数出现了1次, 其他的数全都出现了3次, 这个数的有1的位置上, 1出现的次数肯定为 3 * n + 1, n为任意数. 所以count[i] % 3就获取了当前位置的bit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int singleNumberII(int[] A) {
    int[] count = new int[32];
    for (int n : A) {
        for (int i = 0; i < 32; i++) {
            count[i] += (n >> i) & 1;
        }
    }
    int ans = 0;
    for (int i = 0; i < 32; i++) {
        ans = ans | ((count[i] % 3) << i);
    }
    return ans;
}

另外一种通用做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int singleNumber(int[] nums) {
    //we need to implement a tree-time counter(base 3) that if a bit appears three time ,it will be zero.
    //#curent  income  ouput
    //# ab      c/c       ab/ab
    //# 00      1/0       01/00
    //# 01      1/0       10/01
    //# 10      1/0       00/10
    // a=~abc+a~b~c;
    // b=~a~bc+~ab~c;
    int a = 0;
    int b = 0;
    for (int c : nums) {
        int ta = (~a & b & c) | (a & ~b & ~c);
        b = (~a & ~b & c) | (~a & b & ~c);
        a = ta;
    }
    //we need find the number that is 01,10 => 1, 00 => 0.
    return a | b;
}

Ref: https://discuss.leetcode.com/topic/22821/an-general-way-to-handle-all-this-sort-of-questions

Best one

1
2
3
4
5
6
7
8
public int singleNumber(int[] nums) {
    int ones = 0, twos = 0;
    for (int i = 0; i < nums.length; i++) {
        ones = (ones ^ nums[i]) & ~twos;
        twos = (twos ^ nums[i]) & ~ones;
    }
    return ones;
}

Ref: https://discuss.leetcode.com/topic/2031/challenge-me-thx