面试题40:数组中只出现一次的数字

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


分析

我们先来看一道问题:

一个整型数组中除了一个数字出现了一次之外,其他的数字都出现了两次。请找出这个数字。

这题怎么做呢?记得我们原来有一个模拟面试,当时面试老师就给我出了这么一道题目。我当时冥思苦想绞尽脑汁花了十几分钟写出来,结果老师看都没看,问我:你想两个相同的数字有什么特征?我立马就想起来了。因为两个相同的数字的异或结果为0!有了这个思路,结果我只花了几分钟的时间,用了原来四分之一的代码量就写出来了,确实简洁啊!

所以这道题也可以用相同的方法,将数组中的所有值异或过去,最后的结果肯定为两个只出现一次的数字的异或值!并且这给值肯定不为0.也就是至少有一位为1,这两个数的这一bit位肯定不相同。所以我们可以按照这一位是否为1将数组中的值分为两堆,对这两堆值分别求异或,最后的两个结果就是我们要找的数字。

代码如下:

{
    int i,index=1;
    for(i=0;i<8*sizeof(int);++i)
    {
        if((num &amp; (index<<i)) ==0)
            continue;
        else
            break;
    }
    return i;
}

bool IsBit1(int num,int pos)
{
    return num&amp;(1<<pos);
}

void FindNumbersAppearOnce(const vector<int>&amp; v,int&amp; n1,int&amp; n2)
{
    int i,res=0;
    for(i=0;i<v.size();++i)
    {
        res^=v[i];
    }
    int n=FindFirstBitIs1(res);
    n1=n2=0;
    for(i=0;i<v.size();++i)
    {
        if(IsBit1(v[i],n))
        {
            n1^=v[i];
        }
        else
        {
            n2^=v[i];
        }
    }
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")