题目意思:一个int数组,有一个数只出现一次,其他数均出现三次,找到这个唯一数

思路:

  1.将所有数用2进制表示,计算每一位的数字和  1*3*n1+0*3*n2+c   唯一数对应位的数字(0或者1)

   要求具有牢固的位运算基础

  eg  10001010  10001010 10001010

      10101001   10101001 10101001

11001010                   7,1,3,0,7,0,4,3 则唯一数为1,1,0,0,1,0,1,0

 class Solution {
public:
int singleNumber(vector<int>& nums) {
int a[]={};
int ans=;
for(int i=;i<;++i){
for(int j=;j<nums.size();++j){
a[i]+=((nums[j]>>i)&); //将数右移i位与1&操作,可得到该数对应位的数
}
ans=(ans|(a[i]%)<<i); //将1011100之类的二进制数左移再进行|操作,可得到其表示的10进制数
}
return ans;
}
};

时间复杂度:O(32n)

2.使用3个变量one,two,three

    科普一下:1001&1100=1000(统计出两个数中都为1的地方)

           1001^1100=0101(统计出两个数中只有1个1的地方)

 class Solution {
public:
int singleNumber(vector<int>& nums) {
int one=,two=,three=;
for(int i=;i<nums.size();++i){
two|=(one&nums[i]); //得到出现2次的
one^=nums[i]; //得到出现1次的
three=one&two; //得到出现3次的
one&=~three; //将出现3次的去掉
two&=~three; //将出现3次的去掉
}
return one;
}
};

时间复杂度:O(n)

04-23 01:15