Offer56：数组中数字出现的次数

题目：数组中只出现一次的数字。一个整形数组里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度为O(1)。

分析：异或运算的性质：任何一个数字异或它自己都等于0。 现在考虑一个整形数组里除了一个数字之外，其他数字都出现了两次的情况。我们可以从头到尾依次异或数组中的数字，那么所有出现两次的数字的异或结果都为0，最终的结果刚好是那个只出现一次的数字。对于本题也可用相同的思路，如果将数组中的数字全部异或，最终得到的数字肯定不为0，因为要求得的两个数字不相同。我们假设这两个数分别为a和b,它们异或的结果是y = a ^ b,那么y的二进制表示中至少有一位为1,记为第n位。这样我们可知a和b的第n位有一个是0，另一个是1，那么我们可以把这个数组中的所有数字以它们的二进制表示的第n位为标准，分成两类；一类它们的第n位数字为0，另一类它们的第n位数字为1。这样就可以将同一个数组中求两个不同数字的问题转化为在一个数组中求一个不同数字的这样一个更简单的问题了。

代码：
    void FindNumsAppearOnce(int data[],int length,int* num1,int* num2){
    if(date == nullptr || length < 2) return;
    
    int resultExclusiveOr = 0;
    for(int i = 0;i < length;++i){
        resultExclusiveOr ^= data[i];
    }

    unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOr);

    *num1 = *num2 = 0;
    for(int j = 0;j < length;++j){
        if(IsBit1(data[j],indexOf1)){   //如果当前数字第indexOf1为1，则与num1分为一组异或
            *num1 ^= data[j];
        }
        else{
            *num2 ^= data[j];        //否则与num2分为一组异或，最终的结果则为num1和num2
        }
    }
}


    unsigned int FindFirstBitIs1(int num){      //返回num的二进制表示从小端开始第一个为1的比特位

    int indexBit = 0;
    while(((num & 1)== 0) && (indexBit < 8 * sizeof(int))){
        num = num >> 1;
        ++indexBit;
    }
    return indexBit;
}

    bool IsBit1(int num,unsigned int indexBit){   //判断num的第indexBit位是不是1
        num = num >> indexBit;
        return (num & 1);
}

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

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