56-II. 数组中数字出现的次数 II
1. 描述
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
2. 例子
示例 1:
输入：nums = [3,4,3,3]
输出：4
示例 2:
输入：nums = [9,1,7,9,7,9,7]
输出：1
3. 限制
- 1 <= nums.length <= 10000
- 1 <= nums[i] < $2^{31}$
4. 题解
n = m_nums.size()
时间复杂度: O(n)
空间复杂度: O(1)
我们统计每个二进制数字中 1 左移 0 ~ 31 位的个数，然后除结果外，每个数字都出现三次，所以他们的任意二进制位都出现三次。所以将他们的二进制位出现次数对三取余，有余数的就是那个唯一出现一次的数字含有的二进制位。
只要改变取余的数字，就可以求得其他数字出现任何次时仅有一个数字出现一次的题。
为了性能，应当把 map 换成低级数据结构数组。
class Solution
{
public:
// int singleNumber(vector<int>& nums)
int singleNumber(vector<int> &i_nums)
{
unordered_map<int, int> leftMoveDigitsCount;
for(int i = 0; i < i_nums.size(); i++)
{
for(int j = 0; j < 32 && (1 << j) <= i_nums[i]; j++)
{
if((1 << j) & i_nums[i])
leftMoveDigitsCount[j]++;
}
}
int uniqueNumber = 0;
for(int i = 0; i < 32; i++)
{
if(leftMoveDigitsCount[i] % 3)
uniqueNumber += (1 << i);
}
return uniqueNumber;
}
};