除了一个数出现一次外所有数均出现n次的问题

2016-12-07 08:24:18来源:CSDN作者:castle_kao人点击

第七城市

传授我膜法的长者的长者曾经说过,做事情一定要做到极致,不光要做到庖丁解牛,还要举一反三。于是我总结了一些有关于除了一个数出现m次外,所有数出现n次的问题。先上第一题:

题目1:给定一个包含n个整数的数组,除了一个数出现一次外,所有整数均出现两次,找出这个只出现一次的整数。

坦白的说,你所能想到的什么先排序再比较啊、哈希表啊之类的方法,我都想过了。毫无疑问,性能上都有点欠缺。不是时间复杂度太高,就是空间复杂度太高。接下来我要说的方法,时间复杂度O(n),空间复杂度O(1),用的就是位运算方法。(位运算好用到炸裂!)
上代码:

//除了一个数出现一次外,所有整数均出现两次int findTheOne(int A[],int n){    int i,result;    for(result=i=0;i<n;result^=A[i++]);    /*循环遍历并异或数组元素,result得到仅出现一次的整数*/    return result;}

这段代码的充分发挥了异或运算符的作用:两数异或,数值相同的位为0,数值不同的位为1.在这里的作用是:将数组中每个数进行异或运算,当一个数出现两次时,由于这个数每个位都和自己相同,所以这个数和自己异或后得到结果为0.而0同任何一个数x异或的结果都是x。因此,最终result剩下的数值只能是那个出现了一次的整数。
那么如果我们把题目修改一下呢?
题目2:给定一个包含n个整数的数组,除了两个数出现一次外,所有整数均出现两次,找出这两个只出现一次的整数。

嗨呀,好气啊~~上面那个套路不管用了,如果还是遍历异或的话,最后得到的结果则是两个仅出现一次的数相互异或的结果。如果要解决这个问题,我们可以用一下分治的思想。
比如,数组中有两个仅出现一次的数分别为A和B,(A和B肯定是不一样的,不然就不能叫出现一次了)A和B在二进制数值上肯定某一位是1、某一位是0.那么,如果我们从低位开始,找到了这个数值不一样的位(设为bit),我们就可以将整个数组分为两类:
1. bit位为1的数。
2. bit位为0的数。
这样我们再遍历一遍数组,通过上述的条件筛选就可以将两个数分到两个不同的组中。而不管哪个组中,其他数出现的次数都是偶数次,因此可以像上一道题那样,通过异或运算将其消除,最终剩下我们想要的整数。
代码描述:

void showTheTwo(int A[],int n){    int i,j,result;    for(result=i=0;i<n;result^=A[i++]);    /*result中为两个仅出现一次的整数的异或结果*/    for(j=1;!(result&j);j<<=1);    /*循环相与,从低位开始找到result中第一个1,j存放该位*/    for(result=i=0;i<n;i++)        if((A[i]&j)==0)//若当前元素该位不为1,同result异或            result^=A[i];    printf("first:%5d/n",result);//输出当前result    for(result=i=0;i<n;i++)        if((A[i]&j)!=0)//若当前元素该位为1,同result异或            result^=A[i];    printf("second:%5d/n",result);//输出当前result}       

其他元素出现偶数次的解决办法看来已经了解了,那么出现奇数次呢?

题目3:给定一个包含n个整数的数组,除了一个数出现一次外,所有整数均出现三次,找出这个只出现一次的整数。

这次更麻烦了,所有整数出现的次数都为奇数次,无法用数的偶数次异或来消除重复数了。这个时候就不能单纯的用相互的位运算来解决了。
我们先来分析一下:对于出现了三次的整数,它的二进制的每一位1出现的次数都是3的整数倍。如果我们可以将具有这个特点的位清0,剩下的就是那个出现一次的数了。那么我们现在要解决的问题就成了如何找到这样出现了三次的整数。
这里我们定义三个变量ones,twos,threes。他们的作用是:
1. ones:用来记录到当前计算的变量为止,二进制1出现奇数次的数位。(ones是一个int 型变量,但是它同样使用二进制表示,相当于其他类似方法中用32位数组来存储每一位的0或1.以下的twos和threes的本质与之相同,不再赘述。)
2. twos:用来记录到当前计算的变量为止,二进制1出现偶数次的数位。
3. threes:将ones和twos相与,若某位为1,说明该位的1出现3次,需被消除。故将两变量相与结果取反,赋值给threes。之后用threes清除ones和twos相应的位。

我们先来看代码:

int findTheOne(int A[],int n){    int i,ones=0,twos=0,threes=0;   //ones:二进制1出现奇数次的位                                    //twos:二进制1出现偶数次的位                                    //threes:用来处理二进制1出现三次的位    for(i=0;i<n;i++)        //遍历数组    {        twos|=(ones&A[i]);  /*                            //将ones值同当前元素相与,得到的结果,                            //为遍历到当前变量为止,二进制1出现偶数次的位,                            //将结果同twos相或,即统计所有二进制1出现偶数次的位                            */        ones^=A[i];         /*                            //将ones值同当前元素异或,结果为二进制1出现奇数次的位,                            //将结果赋值给ones存储                            */        threes=~(ones&twos);/*                            //将ones和twos相与,即将之前出现的偶数次的位同本次出现                            //的位相与,得到出现三次的位。将结果按位取反,赋给threes                            */        ones&=threes;       /*                            //本操作即是将ones中二进制1出现三次的位清0,其他位保留                            */        twos&=threes;       /*                            //本操作即是将twos中二进制1出现三次的位清0,其他位保留                            */    }    return ones;    //ones中保留的是仅出现一次的整数}

下面我再强调这段代码的几个要点:
1. twos|=(ones&A[i])要在循环的第一句。因为如果ones^=A[i]在此句之前,那么ones将会把异或后的结果参与到赋值twos的运算,结果可能消除ones中出现过1的位,间接影响是twos会丢失出现两次相同数的记录。
2. ones^=A[i]的必要性。例如通过第一次循环ones存入了某个数值,进入第二次循环后,若ones和A[i]某些位相同,则将相应位存入twos中(存入twos中意味着该位出现两次),那么这之后必须用某种运算将ones中的与A[i]相同位清除,否则之后的运算会将ones和twos的相应位比较,某位比较相等会被认为出现了3次。
3. threes=~(ones&twos)的作用:ones和twos相与结果为1的位,即既出现奇数次又出现偶数次的位,结合上面代码可知,这是出现了3次的位。如果将该位清除,则需要将该位置0,执行threes=~(ones&twos)。因此将ones和twos中该位与处理后的threes相与。

其实一开始我也没看懂这代码是什么意思,我看的时候那位神还没有写注释。现在这些注释是我自己加的,目的是方便各位可以理清思路。如果还是没理解,我建议参照着执行结果来看。我把循环中的每一行执行结果都打印了出来,每次循环分为一个段,大家可以对着结果分析分析:
这里写图片描述

如果我把题目拓展成:
题目4:给定一个包含n个整数的数组,除了一个数出现两次外,所有整数均出现三次,找出这个只出现两次的整数。

实际上解法同上题是一样的,只不过这次返回的是twos。你理解了吗?

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台