刷题第12天(LeetCode #137. 只出现一次的数字 II)

刷题第12天(LeetCode  #137. 只出现一次的数字 II)
一、逐位计算:

将nums中的数在二进制中进行处理。对于二进制中的每一位来说,若一个数出现了三次,则此二进制位出现1的次数必为1的倍数。因此将每一二进制位上1出现的次数进行统计后,进行模3运算,得到的就是只出现1次的那个数字在此二进制位上的数值。

代码实现:

class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int ans=0;
        for(int i=0;i<32;i++)
        {
            int count=0;
            for(auto x:nums)
                count+=(x>>i)&1;
            ans+=(count%3)<<i;
        }
        return ans;
    }
};

刷题第12天(LeetCode  #137. 只出现一次的数字 II)
二、位运算:

在任何一个二进制位上,都需要区分出现1次的数字和出现3次的数字。
为满足这个要求,我们可以令二进制位上只出现1次的数,在此二进制位上对应的值为1;而二进制位上出现3次的数,在此二进制位上对应的值为0。我们将这个满足要求的二进制数储存在变量once中。(运算到最后,once其实就是只出现1次的那个数字。)
出现的次数有1次、2次、3次三种清况,可以用两个单位二进制的变量来表示。
once=1,twice=0表示出现1次;
once=0,twice=1表示出现2次;
once=0,twice=0表示出现3次;

关系图:
刷题第12天(LeetCode  #137. 只出现一次的数字 II)
由此我们可以建立满足该关系的运算:

once = ( once ^ x ) & ( ~ twice )
twice = ( twice ^ x ) & ( ~ once )

代码实现:

class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int once = 0, twice = 0;
        for (auto x : nums) 
        {
            once = (once^x)&(~twice);
            twice = (twice^x)&(~once);
        }
        return once;
    }
};

刷题第12天(LeetCode  #137. 只出现一次的数字 II)

上一篇:C++编译期分支选择相关技术


下一篇:研究生英语期末复习(Unit3)