剑指Offer56.II 数组中数字出现的次数II（位运算的性质）

思路：本题最容易想的思路就是哈希表，第二种思路是使用位运算，由于只有一个数只出现了一次，其余数字都出现了三次，那么也就是说除去这个出现一次的数字以外，剩余的数字之和可以被三整除，同时，这些数字在二进制某一位上为1的个数也应该是三的倍数，如果某一位上 1的个数不是3的倍数说明那个只出现一次的数在那一位是1，所以问题就简单起来了。我下面是逐个统计每一位为1的和，然后直接计算答案，等到所有数字都为0之后直接结束算法。

参考代码

 1 public static int singleNumber(int[] nums) {
 2         
 3         int num; // 标志每一位上1的个数
 4         int temp = 0; // 标志目前是第几位，从零算起
 5         int ans = 0; // 最终答案，迭代计算
 6         int len = nums.length;
 7         boolean flag = true; // 当所有数字都为零时退出循环
 8         while(flag){
 9             num = 0;
10             flag = false;
11             for(int j = 0; j < len; j ++) {
12                 if(nums[j] > 0) flag = true;
13                 if(nums[j] % 2 == 1) {
14                     num ++;
15                 }
16                 nums[j] >>= 1;
17             }
18             if(num % 3 != 0) {
19                 ans += Math.pow(2, temp);
20             }
21             temp ++;
22         }
23         return ans;
24     }

View Code