Offer56(二):数组中唯一只出现一次的数字，其他数字都出现三次

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

分析：我们可以用位运算的思路考虑该问题。如果一个数字出现三次，那么它的二进制表示的每一位也出现三次，如果把所有出现三次数字的二进制表示的每一位都分别加起来，那么每一位的和都能被3整除。运算中我们可以把数组中所有的数字的二进制表示的每一位都加起来，如果某一位加起来的和能被3整除，那么那个只出现一次的数字二进制表示中对应的这一位是0,否则是1。

代码：

int FindNumberAppearOnce(int number[],int length){

    if(number == nullptr || lenght <= 0){
        throw new std::exception("invalid input");
    }

    int bitSum[32] = {0};                        //存放二进制每一位的1的个数
    for(int i = 0;i < length;++i){
        int bitMask = 1;
        for(int j = 31;j >= 0;--j){                //计算所有二进制位的1的个数
            int bit = number[i] & bitMask;
            if(bit != 0) bitSum[j] += 1;
            bitMask = bitMask << 1;
        }
    }

    int result = 0;
    for(int i = 0;i < 32; ++i){    //从高位到低位依次计算result
        result = result << 1;        
        result += bitSum[i] % 3;    //如果能被3整除说明result的当前二进制位是0，不能被3整除就说明result的当前二进制位为1(题目保证余数不是0就是1)
    }
    return result;
}

原文地址：https://blog.csdn.net/qq_31165949/article/details/142460223

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！