剑指 Offer 56 - II. 数组中数字出现的次数 II

题目

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

思路

这题是剑指 Offer 56 - I. 数组中数字出现的次数的变体，本题只有一个数num出现一次，其余的均出现三次

三次的话使用异或消无法消除，首先进行一个转换：

1. 首先，将所有数字都看成 32位 的二进制数；
2. 接着，将数组中的所有数字相加。那么，对于"某一位"来说，数值一定是 3N或3N+1 （所有出现3次的数字对该位置的贡献，和一定是0或3，即要么全0要么全1，出现一次的数字对该位置的贡献，一定是0或1）
3. 所以，对该位置的和，用3取余，结果就是出现一次的数字在该位置的值（这种解法是具有通用性的，即出现4次、5次、N次，直接用4、5、N取余即可。）

java代码如下：

class Solution{public int singleNumber(int[] nums){int res = 0;for(int i = 0 ; i < 32; i++){//对于int每一位int bit = 0;//计算该位上的和for(int num : nums){bit += ((num >> i) & 1);//有0出0，全1出1}//对3取余即为res在该位上的值res += ((bit % 3) << i);//左移相当于乘i}return res;}
}