注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(63)-数组中三个只出现一次的数字[算法]  

2012-09-30 20:42:46|  分类: 数组 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:一个数组中有三个数字abc只出现一次,其他数字都出现了两次。请找出三个只出现一次的数字。

分析:在博客http://zhedahht.blog.163.com/blog/static/2541117420071128950682/中我们讨论了如何在一个数组中找出两个只出现一次的数字。在这道题中,如果我们能够找出一个只出现一次的数字,剩下两个只出现一次的数字就很容易找出来了。

如果我们把数组中所有数字都异或起来,那最终的结果(记为x)就是abc三个数字的异或结果(x=a^b^c)。其他出现了两次的数字在异或运算中相互抵消了。

我们可以证明异或的结果x不可能是abc三个互不相同的数字中的任何一个。我们用反证法证明。假设x等于abc中的某一个。比如x等于a,也就是a=a^b^c。因此b^c等于0,即b等于c。这与abc是三个互不相同的三个数相矛盾。

由于xabc都各不相同,因此x^ax^bx^c都不等于0

我们定义一个函数f(n),它的结果是保留数字n的二进制表示中的最后一位1,而把其他所有位都变成0。比如十进制6表示成二进制是0110,因此f(6)的结果为2(二进制为0010)。f(x^a)f(x^b)f(x^c)的结果均不等于0

接着我们考虑f(x^a)^f(x^b)^f(x^c)的结果。由于对于非0nf(n)的结果的二进制表示中只有一个数位是1,因此f(x^a)^f(x^b)^f(x^c)的结果肯定不为0。这是因为对于任意三个非零的数ijkf(i)^f(j)的结果要么为0,要么结果的二进制结果中有两个1。不管是那种情况,f(i)^f(j)都不可能等于f(k),因为f(k)不等于0,并且结果的二进制中只有一位是1

于是f(x^a)^f(x^b)^f(x^c)的结果的二进制中至少有一位是1。假设最后一位是1的位是第m位。那么x^ax^bx^c的结果中,有一个或者三个数字的第m位是1

接下来我们证明x^ax^bx^c的三个结果第m位不可能都是1。还是用反证法证明。如果x^ax^bx^c的第m位都是1,那么abc三个数字的第m位和x的第m位都相反,因此abc三个数字的第m位相同。如果abc三个数字的第m位都是0x=a^b^c结果的第m位是0。由于xa两个数字的第m位都是0x^a结果的第m位应该是0。同理可以证明x^bx^cm位都是0。这与我们的假设矛盾。如果abc三个数字的第m位都是1x=a^b^c结果的第m位是1。由于xa两个数字的第m位都是1x^a结果的第m位应该是0。同理可以证明x^bx^cm位都是0。这还是与我们的假设矛盾。

因此x^ax^bx^c三个数字中,只有一个数字的第m位是1。于是我们找到了能够区分abc三个数字的标准。这三个数字中,只有一个数字满足这个标准,而另外两个数字不满足。一旦这个满足标准数字找出来之后,另外两个数字也就可以找出来了。

这种思路的C++代码如下:

void getThreeUnique(vector<int>& numbers, vector<int>& unique)

{

    if(numbers.size() < 3)

        return;

   

    int xorResult = 0;

    vector<int>::iterator iter = numbers.begin();

    for(; iter != numbers.end(); ++iter)

        xorResult ^= *iter;

 

    int flags = 0;

    for(iter = numbers.begin(); iter != numbers.end(); ++iter)

        flags ^= lastBitOf1(xorResult ^ *iter);

    flags = lastBitOf1(flags);

   

    // get the first unique number

    int first = 0;

    for(iter = numbers.begin(); iter != numbers.end(); ++iter)

    {

        if(lastBitOf1(*iter ^ xorResult) == flags)

            first ^= *iter;

    }

    unique.push_back(first);

   

    // move the first unique number to the end of array

    for(iter = numbers.begin(); iter != numbers.end(); ++iter)

    {

        if(*iter == first)

        {

            swap(*iter, *(numbers.end() - 1));

            break;

        }

    }

   

    // get the second and third unique numbers

    getTwoUnique(numbers.begin(), numbers.end() - 1, unique);

}

 

int lastBitOf1(int number)

{

    return number & ~(number - 1);

}

 

void getTwoUnique(vector<int>::iterator begin, vector<int>::iterator end, vector<int>& unique)

{

    int xorResult = 0;

    for(vector<int>::iterator iter = begin; iter != end; ++iter)

        xorResult ^= *iter;

   

    int diff = lastBitOf1(xorResult);

   

    int first = 0;

    int second = 0;

   

    for(vector<int>::iterator iter = begin; iter != end; ++iter)

    {

        if(diff & *iter)

            first ^= *iter;

        else

            second ^= *iter;

    }

   

    unique.push_back(first);

    unique.push_back(second);

}

上文中getThreeUnique从数组中找出三个只出现一次的数字,而getTwoUnique从数组中找出两个只出现一次的数字。lastBitOf1实现分析中的函数f(n)的功能,它只保留数字n的二进制表示中的最后一位1,而把其他所有位都变成0

在函数getThreeUnique中,我们通过第一个for循环把abc三个数字异或的结果保存到xorResult中,接着在第二个for循环中求出f(x^a)^f(x^b)^f(x^c)并保存到变量flags中。在语句flags=lastBitOf1(flags)求出f(x^a)^f(x^b)^f(x^c)结果的二进制中最后一位是1的位。并根据这一数位求出第一个只出现一次的数字first。接着把first交换到数组的最后,并在数组的前n-1个数字中求出另外两个只出现一次的数字。


博主何海涛对本博客文章享有著作权。网络转载请注明出处http://zhedahht.blog.163.com/。整理出版物请和作者联系。

  评论这张
 
阅读(58950)| 评论(50)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017