题目描述

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

解决方法

将数组中所有数字的同一位置的数位相加，如果数组中所有数字的第i个数位相加之和能被3整除，那么只出现一次的数字的第i位一定是0；如果数组中所有数字的第i个数位相加之和被3除余1，那么只出现一次的数字的第i位一定是1。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> bitSum(32, 0);

        for (int &num : nums)
        {
            for (int i = 0; i < 32; ++ i)
            {
                //用两个for循环把数组中所有数字的同一位置的数位相加
                bitSum[i] += (num >> (31 - i)) & 1;
            }
        }

        int res = 0;
        for (int i = 0; i < 32; ++ i)
        {
            res = (res << 1) + bitSum[i] % 3;   //还原只出现一次的数字
        }

        return res;
    }
};

扩展知识

题目：输入一个整数数组，数组中只有一个数字出现m次，其他数字都出现n次，请找出那个唯一出现m次的数字。假设m不能被n整除。

如果数组中所有数字的第i个数位相加之和能被n整除，那么出现m次的数字的第i个数位一定是0，否则是1。