Single Number II(Medium)

题目：Given an array of integers, every element appears three times except for one. Find that single one. (给一个数组， 里面只有一个数字一次， 其它数字都出现3次，找出这个出现一次的数字，要求时间复杂度为O(n)，空间复杂度为O(1)。)

解题思路：

考虑全部用二进制表示，如果我们把 第 ith 个位置上所有数字的和对3取余， 那么只会有两个结果 0 或 1 (根据题意，3个0或3个1相加余数都为0). 因此取余的结果就是那个 “Single Number”.

public static int findNumberAppearingOnce(int[] numbers) {
        int[] bitSum = new int[32];
        for(int i = 0; i < 32; ++i) {
            bitSum[i] = 0;
        }

        for(int i = 0; i < numbers.length; ++i) {
            int bitMask = 1;
            for(int j = 31; j >= 0; --j) {
                int bit = numbers[i] & bitMask;
                if(bit != 0) {
                    bitSum[j] += 1;
                }

                bitMask = bitMask << 1;
            }
        }

        int result = 0;
        for(int i = 0; i < 32; ++i) {
            result = result << 1;
            result |= bitSum[i] % 3;//k
        }

    return result;
}

上面这个算法也适用于其它数字都出现k次的情况。

改进的算法：

• ones as a bitmask to represent the ith bit had appeared once.
• twos as a bitmask to represent the ith bit had appeared twice.
• threes as a bitmask to represent the ith bit had appeared three times.

• int singleNumber(int A[]) {
      int ones = 0, twos = 0, threes = 0;
      for (int i = 0; i < A.length; i++) {
        //if a bit get one and it occurs again, add it to two
        twos |= ones & A[i];
  
        //means marking the bits emerged 1 or 3 times
        ones ^= A[i];
  
        //对于ones 和 twos 把出现了3次的位置设置为0（取反之后1的位置为0）
        threes = ones & twos;
        ones &= ~threes;
        twos &= ~threes;
     }
    return ones;
  }
  

References:

1 No. 50 - Numbers Appearing Once

2 Constant space solution