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

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
https://leetcode-cn.com/problems/WGki4K/

时间复杂度：32个bit×长度为N的数组，所以时间复杂度是32N。也是O（N）

int singleNumber(int* nums, int numsSize){
    //32个bit×长度为N的数组，所以时间复杂度是32N。也是O（N）
    int arr[32] = {0};
    int count = 0;
    int k = 31;
    for(int i = 0;i<32;i++)
    {
        for(int j = 0;j<numsSize;j++)
        {
            count+=((nums[j]>>i)&1);

        }
        arr[k] = count;
        count=0;
        k--;
    }
    for(int i = 0;i<32;i++)
    {
        arr[i]%=3;
    }
    int ret = 0;
    for(int i = 0;i<32;i++)
    {
        ret|=(arr[31-i]<<i);
    //这种按位或改变二进制位也可以
    //res <<= 1; // 左移 1 位
    //res |= counts[31 - i]; // 恢复第 i 位的值到 res
    }
    return ret;
}

思路：
由于这次其他数字出现的次数是奇数次，全部一起异或无法消除掉其余的数字。因此我们要换种方法。

把数组中所有的数的每一个二进制位加起来放进一个数组，然后%3，最后得到的数字就是那个只出现一次的数字。

为什么呢？由于其他数字都出现了三次，因此它们的那一位二进制位一定是3的倍数。%3相当于把那些重复的位全部减去了，剩下的二进制位就是只出现一次的数字的二进制位。

步骤：

1. 先用按位与把每一位二进制位拿出来并相加存进数组中
2. 再把数组中的数字都%3
3. 用按位或把数组中的数字操作在result上

最后

以上就是无限小松鼠为你收集整理的在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。的全部内容，希望文章能够帮你解决在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。