题意:给一个序列,其中只有1个元素只出现1次,其他的都一定出现3次。问这个出现一次的元素是多少?
思路:
(1)全部元素拆成二进制,那么每个位上的1的个数应该是3的倍数,如果不是3的倍数,则ans的这个位肯定为1。
22ms
class Solution {
public:
int singleNumber(vector<int>& nums) {
int times[]={};
for(int i=; i<nums.size(); i++)
for(int j=; j<=; j++)
if( &(nums[i]>>j) )
times[j]++; int ans=;
for(int i=; i>=; i--)
{
ans<<=;
if(times[i]% ) ans|=;//如果有余数,则保障最低位为1
}
return ans;
}
};
AC代码
(2)用位运算。道理同方法一。为了方便理解,写复杂一点。共需要3个变量,s保存出现过2次的1,one保存出现1次的1,还有一个临时变量t做记录用。
首先,如果s和one中同时出现1,视为该位已经出现了3的倍数个1,要将one和s中该位清零。因为s中的1代表该位已经出现了2次1。
最后,one就是结果,表示一个只出现1次的元素。而s表示一个只出现2次的元素,当然,与此题无关。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int s=, one=;
for(int i=; i<nums.size(); i++)
{
s|=(~(one^nums[i]))&one;//保存出现了2次的1
one^=nums[i];
int t=s&one;//t所有为1的位都要在s和one中对应位清零,因为该位的1出现了3次,下面两步时清除工作。
s&=~t;
one&=~t;
}
return one;
}
};
AC代码