【LeetCode】【剑指offer】【数组中数字出现的次数（二）】

 剑指 Offer 56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

输入：nums = [3,4,3,3]
输出：4
示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1
 

限制：

1 <= nums.length <= 10000
1 <= nums[i] < 2^31

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 

首先我们可以采用map映射的方法，统计所有元素出现的次数，然后将出现次数为1的数据返回。但是同样，这种算法虽然能够完成任务，但是非常低效。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int ,int> record;
        for(auto num:nums)
        {
            record[num]++;
        }
        for(auto num:nums)
        {
            if(record[num]==1)
            {
                return num;
            }
        }
        return 0;
    }
};

这里我们可以采用这样的方法，就是统计全部数据的每一个二进制位上1的个数，然后全部都对3取模。因为我们从题目中知道，只有一个数据出现了一次，其余的数据全部都出现了三次，所以对三取模就相当于将这三个相同的数据全部都抵消掉了，而剩下的恰好就是那个仅出现了一次的数据 

上面是我们的样例数据，从中我们可以观察到就1出现了一次，其余的3和4都出现了三次，此时我们分别将二进制位从右往左数第三位的全部数据相加，第二位的全部数据相加，第一位的全部数据相加

从上面这张表格中，我们可以很清晰地看出从右往左第三位全部相加是3，第二位全部相加是3，第一位全部相加是4，然后我们分别对这些相加的结果取模，就会得到0,0,1， 将这三位拼接起来就是001，也就是我们上面仅出现了一次的数据元素1。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //创建一个大小为32的容器
        //因为我们一个int的大小是4个字节，每个字节又是8个比特位
        vector<int>binary_digit(32);
        //遍历我们的数据
        for(int i=0;i<nums.size();i++)
        {
            //point为我们当前所计算的是第几位的数据
            int point=0;
            //将我们容器中当前位置的数据拷贝出来
            int tmp=nums[i];
            //循环遍历，将这个数据转化成二进制位，然后每一位都加到对应的
            //binary_digit位上
            while(tmp)
            {
                binary_digit[point]+=tmp%2;
                //右移一位，获取下一个比特位的数据
                tmp=tmp>>1;
                //point++，准备存储下一个比特位的数据
                point++;
            }
        }

        //result就是我们要返回的结果
        int result=0;
        //遍历我们的二进制的容器元素，分别将其中的每一位都对3取模，
        //然后将每一位从前到后拼接起来，组成我们的结果
        for(int i=0;i<binary_digit.size();i++)
        {
            result+=(binary_digit[i]%3)*(1<<i);
        }
        return result;
    }
};