题目描述
在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。
请找出那个只出现一次的数字。
你可以假设满足条件的数字一定存在。
思考题:
如果要求只使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?
数据范围
数组长度 [1,1500]。
样例
输入:[1,1,1,2,2,2,3,4,4,4]
输出:3
算法1
(遍历统计二进制中1的个数) $O(32n)$ $O(n\log{n})$
1.统计一下数组中各个位置1出现的次数
2.将1出现的次数对3求余数,其实就得到了答案
3.将count[32]变为int就可以了
C++ 代码
class Solution {
public:
int findNumberAppearingOnce(vector<int>& nums)
{
int count[32];
memset(count,0,sizeof count);
//统计一下各个位置1出现的次数
for(unsigned int x:nums)
{
for(int i=0;i<32;++i)
{
count[i] += x&1;
x= x>>1;
}
}
for(int i=0;i<32;++i)
{
//将3变为m,问题变为:除了一个数字以外,其余数字都出现m次
count[i] = count[i] %3;
}
int res =0;
for(int i=0;i<32;++i)
{
res |= (count[i]<<i);
}
return res;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla