[leetcode hot 150]第一百三十七题，只出现一次的数字Ⅱ

题目：

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

 

由于需要常数级空间和线性时间复杂度，常规的哈希表或者排序方法不适用。可以利用位运算来解决这个问题。具体思路如下：

1. 位运算：

   • 可以利用每个数字的二进制表示。

   • 对于每一位（bit），统计所有数字中该位上1的个数。

   • 如果某一位上的1的个数是3的倍数，那么该位在只出现一次的那个数字中是0，否则是1。

public class no_137 {public static void main(String[] args) {int[] nums = {0, 1, 0, 1, 0, 1, 99};System.out.println(singleNumber(nums));}public static int singleNumber(int[] nums) {int ones = 0, twos = 0;for (int num : nums) {//  更新ones和twosones = (ones ^ num) & ~twos;twos = (twos ^ num) & ~ones;}return ones;}
}