P222 只出现一次的数字

描述#

这个题目说的是，给你一个不为空的整数数组，这个数组中有一个整数只出现了一次，其它的整数都出现了三次，你要找出这个只出现一次的整数。

注意，这个题目要求你的解法是线性时间复杂度以及常量空间复杂度。

比如说，给你的整数数组是：
3, 3, 2, 3, 2, 6, 2
在这个数组中，3 和 2 都出现了三次，而 6 只出现一次，因此你要返回 6。

相关视频：单身数字，只出现一次的两个数字

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int singleNumberSum(int[] nums) {
    int result = 0;
    for (int bit = 0; bit < 32; ++bit) {
      int sum = 0;
      for (int num: nums)
        sum += (num >> bit) & 1;
      if (sum % 3 == 1) result |= (1 << bit);
    }
    return result;
  }

  // Time: O(n), Space: O(1)
  public int singleNumberBit(int[] nums) {
    int ones = 0, twos = 0, threes = 0;
    for (int num: nums) {
      twos |= ones & num;
      ones ^= num;
      threes = ones & twos;
      ones -= threes; // ones &= ~threes;
      twos -= threes; // twos &= ~threes;
    }
    return ones;
  }

}