异或的应用 及剑指offer 面试 40 数组中只出现一次的数字

转载请注明出处:http://blog.csdn.net/ns_code/article/details/27568975

    这篇文章没有代码,介绍的是纯理论的思路。

    异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。它与布尔运算的区别在于,当运算符两侧均为1时,布尔运算的结果为1,异或运算的结果为0。

    异或的性质:

    1、交换律:a^b = b^a;

    2、结合律:(a^b)^c = a^(b^c);

    3、对于任意的a:a^a=0,a^0=a,a^(-1)=~a。

    了解了上面这些,来看看这个,很重要,后面的程序都要用到这个结论:

    对于任意的a,有a^b^c^d^a^k = b^c^d^k^(a^a) = b^c^d^k^0 = b^c^d^k,也就是说,如果有多个数异或,其中有重复的数,则无论这些重复的数是否相邻,都可以根据异或的性质将其这些重复的数消去,具体来说,如果重复出现了偶数次,则异或后会全部消去,如果重复出现了奇数次,则异或后会保留一个。

    下面来看两道题目:

     1、1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?

    当然,这道题,可以用最直观的方法来做,将所有的数加起来,减去1+2+3+...+1000的和,得到的即是重复的那个数,该方法很容易理解,而且效率很高,也不需要辅助空间,唯一的不足时,如果范围不是1000,而是更大的数字,可能会发生溢出。

    我们考虑用异或操作来解决该问题。现在问题是要求重复的那个数字,我们姑且假设该数字式n吧,如果我们能想办法把1-1000中除n以外的数字全部异或两次,而数字n只异或一次,就可以把1-1000中出n以外的所有数字消去,这样就只剩下n了。我们首先把所有的数字异或,记为T,可以得到如下:

T = 1^2^3^4...^n...^n...^1000 = 1^2^3...^1000(结果中不含n)

    而后我们再让T与1-1000之间的所有数字(仅包含一个n)异或,便可得到该重复数字n。如下所示:

T^(a^2^3^4...^n...^1000) = T^(T^n) = 0^n = n

    这道题到此为止。

    2、一个数组中只有一个数字出现了一次,其他的全部出现了两次,求出这个数字。

    明白了上面题目的推导过程,这个就很容易了,将数组中所有的元素全部异或,最后出现两次的元素会全部被消去,而最后会得到该只出现一次的数字。

    该题目同样可以该为如下情景,思路是一样的:数组中只有一个数字出现了奇数次,其他的都出现了偶数次。

题目描述:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。输入:

每个测试案例包括两行:

第一行包含一个整数n,表示数组大小。2<=n <= 10^6。

第二行包含n个整数,表示数组元素,元素均为int。

输出:对应每个测试案例,输出数组中只出现一次的两个数。输出的数字从小到大的顺序。样例输入:

8
2 4 3 6 3 2 5 5

样例输出:

4 6

    思路:上篇博文中已经了解到异或去重的原理,而且知道如果只有一个只出现一次的数字的求法,但这里是有两个只出现一次的数字,我们便要想办法把他分为两个子数组,每个子数组中包含一个只出现一次的数字,其他的数字都出现了两次。剑指offer上的思路很巧妙,依然从头到尾异或所有的数字,这样得到的结果实际上就是两个只出现了一次的数字异或的结果,我们在异或后的结果中找出其二进制中最右边为1的位,该位既然为1,说明异或的两个数字对应的该位肯定不同,必定一个为1,一个为0,因此我们可以考虑根据此位是否为1来划分这两个子数组,这样两个只出现一次的数字就分开了,但我们还要保证出现两次的数字都分到同一个子数组中,肯定不能两个重复的数字分在两个不同的子数组中,这样得到的结果是不对的,很明显,相同的数字相同的位上的值是相同的,要么都为1,要么都为0,因此我们同样可以通过判断该位是否为1来将这些出现两次的数字划分到同一个子数组中,该位如果为1,就分到一个子数组中,如果为0,就分到另一个子数组中。这样就能保证每个子数组中只有一个出现一次的数字,其他的数字都出现两次,分别全部异或即可得到这两个只出现一次的数字。时间复杂度为O(n)。

    另外,所有元素异或后,在找出最右边为1的时,我用的比剑指offer上更简洁的代码,主要用到了下面的结论:

对于一个数字X,X&(-X)之后得到的数字,是把X中最右边的1保留下来,其他位全部为0。注意,这里的-X是X的相反数,-X=~X+1,这里的~X意思是对X所有位取反,不要将二者弄混了。

    下面是AC的代码:

[cpp] view plaincopy

  1. #include<stdio.h>
  2. #include<stdbool.h>
  3. /*
  4. 返回num的最低位的1,其他各位都为0
  5. */
  6. int FindFirstBit1(int num)  
  7. {  
  8. //二者与后得到的数,将num最右边的1保留下来,其他位的全部置为了0
  9. return num & (-num);  
  10. }  
  11. /*
  12. 判断data中特定的位是否为1,
  13. 这里的要判断的特定的位由res确定,
  14. res中只有一位为1,其他位均为0,由FindFirstBit1函数返回,
  15. 而data中要判断的位便是res中这唯一的1所在的位
  16. */
  17. bool IsBit1(int data,int res)  
  18. {  
  19. return ((data&res)==0) ? false:true;  
  20. }  
  21. void FindNumsAppearOnce(int *arr,int len,int *num1,int *num2)  
  22. {  
  23. if(arr==NULL || len<2)  
  24. return;  
  25. int i;  
  26. int AllXOR = 0;  
  27. //全部异或
  28. for(i=0;i<len;i++)  
  29.         AllXOR ^= arr[i];  
  30. int res = FindFirstBit1(AllXOR);  
  31.     *num1 = *num2 = 0;  
  32. for(i=0;i<len;i++)  
  33.     {  
  34. if(IsBit1(arr[i],res))  
  35.             *num1 ^= arr[i];  
  36. else
  37.             *num2 ^= arr[i];  
  38.     }  
  39. }  
  40. int main()  
  41. {  
  42. static int arr[1000000];  
  43. int n;  
  44. while(scanf("%d",&n) != EOF)  
  45.     {  
  46. int i;  
  47. for(i=0;i<n;i++)  
  48.             scanf("%d",arr+i);  
  49. int num1,num2;  
  50.         FindNumsAppearOnce(arr,n,&num1,&num2);  
  51. if(num1 < num2)  
  52.             printf("%d %d\n",num1,num2);  
  53. else
  54.             printf("%d %d\n",num2,num1);  
  55.     }  
  56. return 0;  
  57. }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Leetcode名企之路

【Leetcode】59. 螺旋矩阵 II

给定一个正整数 n,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

15730
来自专栏数据库新发现

思科CEO钱伯斯:我非常尊敬华为

--------------------------------------------------------------------------------...

31610
来自专栏黄成甲

怎样成为解决问题的高手(连载一)

什么是问题?一言以蔽之,问题来源于现实与目标的差距。因此,问题产生的原因可能是不清楚目标是什么;还可能是不知道差距产生的原因是什么;或者虽然知道差距产生的原因,...

35140
来自专栏進无尽的文章

益思维-早期苹果员工胸牌背面写的11条“成功法则”

早期苹果员工胸牌背面写的11条“成功法则”这个胸牌的背面写着11条成功法则,其中每一条文字都充满了正能量。从中我们可以看到一些触动人心的感觉。

9020
来自专栏進无尽的文章

什么才是优秀的网站用户界面设计

16320
来自专栏黄成甲

怎样科学地和人相处?

按照约定俗成的说法,一般跟人打交道有两个规则,一个是“黄金法则”,一个是“白银法则”。黄金法则并不适合现代社会对陌生人使用。因为你觉得好的东西别人不一定觉得好。...

15920
来自专栏一个会写诗的程序员的博客

服务网格 Pattern: Service Mesh

自从几十年前首次引入以来,我们了解到分布式系统能够实现我们之前甚至无法思考的用例,但它们也会引入各种新问题。

14320
来自专栏数据库新发现

第十三届搞笑诺贝尔奖(IgNobel)新鲜出炉

第十三届搞笑诺贝尔奖(IgNobel)新鲜出炉 中广网 10月04日 09:48

18930
来自专栏知道一点点

20种新颖的按钮风格和效果【附源码】

Codrops 给我们分享了一组新鲜的按钮样式和效果的集合。它们中的大部分效果都使用了 CSS3 过渡和伪元素,他们都有一个共同点,那就是都具有简单性,没有太多...

16610
来自专栏计算机编程

2018-03-14 致敬霍金

  在黑洞领域,没有人知道这个怪兽是个什么东西,自从霍金给出“霍金辐射”与“奇点定理”过后,人们终于逐渐揭开了这宇宙中最为神秘的天体。在这里再次缅怀一下虽然坐着...

15120

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励