前言上次我们讲了异或运算的妙用。其实简单来说，就是记住XOR运算的三个特性0和任意数N进行XOR运算，结果为N。如果任意数N与自身异或，结果为0。异或运算满足交换律和结合律。当然，如果你对这些特性不是很了解，或者对异或运算不是很熟悉，还是建议先看这篇文章。位运算的妙用——异或运算。“废话少说，还是看面试真题吧。”Q1：在一个数组中，一个数出现奇数次，其他数出现偶数次。如何找到这个数字“要求：时间复杂度O(n)”。其实这个问题还是比较容易理解的。让我们直接来看一个例子。比如在数组[1,1,2,2,3]中，只需要找到3，因为3只出现了一次，也就是奇数次，其余的数字都出现了偶数次。比如数组[1,1,2,2,3,3,3]也可以找出3。其实最简单的方法就是暴力破解的方法。我们可以再次循环这个数组，在另一个数组中记录每个数字的出现次数（需要一个记录这个数字和这个数字出现的次数的map），然后再循环另一个数组，找出是奇数的出现次数.“但是这个题目是有要求的”，时间复杂度要求是O(n)，也就是说要循环一圈才能得出结果，所以暴力破解的方法肯定是行不通的。所以我们要转变观念。运用异或运算法则解题首先，在异或运算中，“任意数N与自身异或，结果为0”，所以我们对数组中的所有数进行异或运算，所有“偶数”numberofoccurrences数字异或运算的结果为0”，我们来看一个例子（因为异或运算满足交换律，所以不需要关心数字出现的位置）。arr=[a,b,b,c,c,c,c,d,d……]比如看上面的数组，我们对每个元素进行异或运算。temp=a^b^b^c^c^c^c^d^d因为“任意数N与自身异或，结果为0”，所以除a外的数，异或结果为0。所以结果为allXORoperationsonceis:temp=a^0其实简单来说就是两个b的异或结果为0，两个c的异或结果为0（上面的case写了4个c，其实结果是一样的)，两个d的异或结果为0，则所有数向下异或，发生偶数次的异或运算结果为0。另外，根据“0和任意数N进行异或运算，结果为N”，所以：temp=a^0=a，所以最后的temp就是我们要找的数，源码如下：funcfindOddTimesNumber(arr[]int)(tempint){fori:=0;我<长度(arr);i++{temp^=arr[i]//temp默认为0，相当于0^a（出现奇数次的数）^b^b^c^c.......,根据上面的计算分析，结果是a，也就是我们要求的数}returntemp}如果你已经看懂了上面的问题，那么“我们加大难度，看更复杂的情况”。Q2：数组中有两种数出现奇数次，其他数出现偶数次，如何求这个数“要求：时间复杂度O(n)”。这道题和上面那道题的区别在于“有两种数字出现的次数是奇数”。arr=[a,b,c,c,d,d,e,e...]其实就是简单的在上面的数组arr中找出a和b。异或一次，那么结果一定是a^b。我们的目的是分别找到a和b。当然，这种方法是行不通的，或者说是不行的。但是上面计算后的结果：temp=a^b（其余出现偶数次的数异或运算结果全为0）首先，因为a和b是两种数，所以“a一定不等于b”，所以“a^b的结果必须大于0”，换句话说，a^b的结果，即“temp的二进制表示必须至少有一位为1”。这句话很重要。理解了这句话我们继续往下看。比如temp的第7位是1，也就是说a和b的第7位不一样，一个是0，一个是1。那我们能不能按照第七位是不是1来分组，“每组出现的偶数个数异或结果为0”，所以最后两组剩下的就是我们需要的数了。我们先来看一个方法。res:=num&(^num+1)上述方法的目的是获取num最左边的1。这是什么意思？比如num是1011011，那么最左边的1就是00000001，我们用代入的方法一步步计算。所以最终算法如下：funcfindTwoOddTimesNumber(arr[]int)(left,rightint){fori:=0;我<长度(arr);i++{left^=arr[i]}temp:=left&(^left+1)//获取最左边的1fori:=0;我<长度(arr);i++{ifarr[i]&temp==0{//根据某位是否为1分组right^=arr[i]}}left=right^leftreturnleft,right}
