剑指offer56:数组中数字出现的次数

第一题:

剑指offer56:数组中数字出现的次数

 只能说这是道数学题,能想到异或操作tql,详细思路可以参考:

力扣

以下是代码:

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int ans=0;
        for(int &n:nums)
        {
            ans^=n;
        }
        int num=1;
        while((num&ans)==0)
        {
            num<<=1;
        }
        int a=0,b=0;
        for(int &n:nums)
        {
            if(n&num)
            {
                a^=n;
            }
            else
            {
                b^=n;
            }
        }
        return vector<int>{a,b};
    }
};

结果如下:

剑指offer56:数组中数字出现的次数

 第二题:

剑指offer56:数组中数字出现的次数

emmm,这里要怎么想呢,比如把所有的数字化成二进制的,那么在某一位上,如果单独的那一个数为0,那么那个位置上的所有1,0之和肯定是3的倍数,按照这个思想,统计出每一位上面的和,如果是3的倍数,则对应数的位置上面是0,否则是1。

代码如下所示:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> bit(32,0);
        for(int n:nums)
        {
            int i=0;
            while(n)
            {
                bit[i]+=n&1;
                n>>=1;
                ++i;
            }
        }
        int res=0;
        for(int i=0;i<32;++i)
        {
            res<<=1;
            res|=bit[31-i]%3;
        }
        return res;
    }
};

 结果如下所示:

 剑指offer56:数组中数字出现的次数

 

上一篇:Leetcode数据结构入门第四天(数组)


下一篇:Leetcode学习1