数组中只出现一次的数字

题目:一个整型数组里除了两个数字以外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(N),空间复杂度是O(1)。

例如,在数组{2,4,3,6,3,2,5,5}中,只有4,6出现了一次,其他数字都是成对出现。所以结果应该是4和6。

分析题意,在学C语言的时候我们做过一道题,一个数组中只有一个数字出现了一次,其他数字都是成对出现。这道题我们很容易想到用抑或的性质,相同为0,相异为1。那么最终的结果就是整个数组抑或产生的结果。

那么现在我们需要找到两个只出现一次的数字,我们可以把数组分为两个子数组,在这两个子数组中分别存放一个只出现了一次的数字。
我们还是先将整个数组抑或,因为其他数字都是成对出现,所以会抵消,那么得到的结果就是那两个只出现一次的数字抑或的结果。由于这两个数字不一样,那么抑或的结果必然不为0,也就是说在这个结果数字的二进制中至少有一个1,我们在这个结果数字中找到第一个为1的位置,记为第n位。接下来我们就可以以第n位是不是为标准将数组分为两个子数组,第一个数组中每个数字的第n位是1,第二个子数组中每个数字的第n位都是0,那么相同的数字肯定被分到了同一个数组中。

比如,数组是{2,4,3,6,3,2,2,5,5},对整个数组抑或后,产生的结果用二进制表示是0010。抑或得到的结果中倒数第二位是1,于是我们根据倒数第二位是不是1将数组分为两个数组。第一个数组{2,3,6,3,2}中所有数字的倒数第二位都是1,而第二个数组{4,5,5}中所有数字的倒数第二位都是0。接下来只要分别毒地两个数组进行抑或,就能找到这两个只出现一次的数字。

//找到第一个为1的bit位
unsigned int FindFirstBitIs1(int num)
{
    int indexBit = 0;
    while (((num & 1) == 0) && (indexBit < 8 * sizeof(int)))
    {
        num = num >> 1;
        ++indexBit;
    }
    return indexBit;
}

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


void FindNumsAppearOnce(int data[], int length, int* num1, int* num2)
{
    if (data == NULL || length < 2)
        return;
    int resultExclusiveOr = 0;
    for (int i = 0; i < length; ++i)
    {
        resultExclusiveOr ^= data[i];//整个数组抑或之后的结果
    }
    //找到第一个为1的bit位
    unsigned int indexOf1 = FindFirstBitIs1(resultExclusiveOr);
    *num1 = *num2 = 0;
    for (int j = 0; j < length; ++j)
    {
        if (IsBit1(data[j], indexOf1))
            *num1 ^= data[j];
        else
            *num2 ^= data[j];
    }
}
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院