剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣(LeetCode)
在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
思路分析:
每一个数字在某些位上可能是1,也可能是0。因为除一个数字外,其他数字都出现了三次,因此我们可以统计每一位上1总共有多少个,然后对3取模,得到的就是出现一次的数字在该位的值。
方法一:
利用一个32位的数组统计每一位1出现的个数
点击查看代码
class Solution {
public:
int count[32];
int singleNumber(vector<int>& nums) {
for (auto i=nums.begin();i!=nums.end();i++)
{
unsigned int num=*i;
unsigned int res=1;
//cout<<"------"<<endl;
for (int j=0;j<32;j++)
{
if (res&num){
count[j]++;
//cout<<j<<endl;
}
res<<=1;
}
}
int ans=0;
for (int i=0;i<32;i++)
{
int res=(count[i]%3)<<i;
ans|=res;
}
return ans;
}
};
时间复杂度O(n*32),空间复杂度O(1),但是该方法的实现效率较低。对于这一类问题:一个数出现m次,其他数均出现n次,都可以用这个方法解决。
方法二:
整体思路同方法一,但是求解次数时,方法一的效率太低,我们可以构造一个有限自动机,然后通过位操作提高效率。
具体分析:
-
我们对某一位进行分析,因为最后答案是对3取模,因此我们可以每次处理完一个数之后,都进行取模。这样的话,每一位可能出现的情况就是:0,1,2 这三种状态之一,开始时,该位为0,然后遍历数组,当遇到1时,转换到下一个状态,当遇到零时,状态不变。
-
因为我们想要利用位运算,而三种状态是不可能用一位表示的,因此需要用两位表示,这时状态就在 00,01,10 这三个状态之间转换。
-
我们可以设高位为a,低位为b。
-
先考虑b,转换情况如下,注意不存在11这种状态:
b a n ans 1 0 0 1 1 1 0 不存在 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 不存在 根据表格可以得到:ans=(~a) b (~n) | (~b) (~a) n=(~a) (b^n)
综上:b=(~a)(b^n) -
我们接着考虑a,a的值不仅与自己和n有关,还与b的新值有关:
a b n ans 1 0 0 1 1 1 0 不存在 0 1 0 0 0 0 0 0 1 0 1 0 1 1 1 不存在 0 1 1 0 0 0 1 1 可以得到 ans=a(~b) (~n) + (~a) (~b) n=(~b)(a^n);
-
对每一位都有如上的结果。然后我们考虑如何还原得到出现一次的数,因为该数只出现了一次,因此它的某一位只能是0或者1,不可能出现前面的10这种情况,这种情况只会出现在计算的过程中,在最后的结果中某一位要么是0要么是1.因此要得到这个数,只需要将每一位的b返回即可。
点击查看代码
class Solution {
public:
int singleNumber(vector<int>& nums) {
int a=0;
int b=0;
for (auto i=nums.begin();i!=nums.end();i++)
{
b=(~a)&(b^(*i));
a=(~b)&(a^(*i));
}
return b;
}
};