前言

上次咱們聊了聊異或運算的妙用，其實簡單來說，就是記住異或運算的三個特性

• 0和任何數(shù)N進行異或運算，結(jié)果為N。
• 任何數(shù)N和自己進行異或運算，結(jié)果為0。
• 異或運算滿足交換律和結(jié)合律 當(dāng)然如果您對這幾個特性不是很了解，或者不是很熟悉異或運算的話，建議先看看這篇文章?? 位運算的妙用--異或運算??。

「閑話不用多說，咱們來看面試真題」

Q1:一個數(shù)組中有一種數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，怎么找到這一個數(shù)

「要求：時間復(fù)雜度O(n)」。

其實這道題還是比較好理解的。

咱們直接來舉例子。

比如數(shù)組[1,1,2,2,3] 把3找出來即可，因為3只出現(xiàn)了1次，為奇數(shù)次，其余的數(shù)字出現(xiàn)的都為偶數(shù)次。

比如數(shù)組[1,1,2,2,3,3,3] 同樣把3找出來即可。

其實最簡單的方法，也就是暴力破解法，咱們可以把數(shù)組循環(huán)一遍，把每個數(shù)字出現(xiàn)的數(shù)字記錄在另一個數(shù)組中(需要記錄數(shù)字和該數(shù)字出現(xiàn)的次數(shù)的map)，然后循環(huán)另一個數(shù)組找出出現(xiàn)次數(shù)為奇數(shù)的即可?！傅沁@個題目有要求」，時間復(fù)雜度要求為O(n)，也就是說只能循環(huán)一次就把結(jié)果就找出來，所以暴力破解法肯定是行不通的。所以咱們必須得換個思路。

利用異或運算的規(guī)律來解題

首先，在異或運算中「任何數(shù)N和自己進行異或運算，結(jié)果為0」,所以我們把數(shù)組中的所有數(shù)進行異或運算，所有「出現(xiàn)偶數(shù)次的數(shù)字進行異或運算結(jié)果為0」，咱們來看一個例子(因為異或運算滿足交換律，所以不用關(guān)心數(shù)字出現(xiàn)的位置)。

arr = [a,b,b,c,c,c,c,d,d.............]

比如看上述數(shù)組，咱們來對每個元素進行異或運算。

temp = a ^ b ^ b ^ c ^ c ^ c ^ c ^ d ^ d

因為「任何數(shù)N和自己進行異或運算，結(jié)果為0」所以除了a以外的數(shù)字，異或結(jié)果為0。

所以全部進行異或運算一次的結(jié)果為：

temp = a^0

其實簡單的說就是兩個b異或結(jié)果為0，兩個c異或結(jié)果是0(上面的case寫了4個c，其實結(jié)果是一樣的)，兩個d異或結(jié)果為0，那么所有的數(shù)字異或下來，出現(xiàn)偶數(shù)次的結(jié)果異或運算的結(jié)果就為0。

另外根據(jù)「0和任何數(shù)N進行異或運算，結(jié)果為N」所以：

temp = a^0 = a

所以最終的temp則為我們需要找到的數(shù)，源碼如下：

func findOddTimesNumber(arr []int) (temp int) {
 for i := 0; i < len(arr); i++ {
  temp ^= arr[i] //temp默認為0  相當(dāng)于0^a(出現(xiàn)奇數(shù)次的數(shù)字)^b^b^c^c.......,根據(jù)上述運算的解析，結(jié)果為a，也就是我們想找到的數(shù)
 }
 return temp
}

如果上面的題您已經(jīng)明白了，那么「接下來咱們加大難度，看一種更復(fù)雜的情況」。

Q2:一個數(shù)組中有兩種數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，怎么找到這一個數(shù)

「要求：時間復(fù)雜度O(n)」。

這道題和上面那道題的區(qū)別就在于「有兩種數(shù)字出現(xiàn)了奇數(shù)次」。

arr = [a,b,c,c,d,d,e,e......]

其實簡單說也就是要把上面數(shù)組arr中的a和b分別找出來，如果按照前面的方法全部異或一次，那么結(jié)果肯定為a^b,我們的目的是把a和b分別找出來，這種辦法當(dāng)然是行不通的，或者說是不夠的。

但是上面計算之后的結(jié)果：

temp= a^b(其余出現(xiàn)偶數(shù)次的數(shù)字進行異或運算結(jié)果都為0)

首先，因為a和b是兩種數(shù)，所以「a肯定是不等于b的」,所以「a^b的結(jié)果肯定大于0」,換句話說a^b的結(jié)果，也就是「temp的二進制表現(xiàn)肯定是至少有一位是1的」。這句話很重要，明白了這句話咱們就繼續(xù)往下看。

比如temp的第7位為1，那就說明a和b的第7位是不一樣的，一個為0，一個為1。那么咱們是不是可以通過第7位是否為1，然后進行分組，「每個分組中出現(xiàn)的偶數(shù)次的數(shù)字的異或結(jié)果都是0的」，所以最后兩個分組各自剩下的就是所需數(shù)字了。

咱們先來看一個方法。

res := num & (^num + 1)

上述方法的目的是獲取num最左邊的1。什么意思呢?比如num是 1011011，那么他最左邊的1 就是00000001。

咱們用一個代入的方式一步一步的計算試試。

所以最后算法如下：

func findTwoOddTimesNumber(arr []int) (left, right int) {
 for i := 0; i < len(arr); i++ {
  left ^= arr[i]
 }
 temp := left & (^left + 1)  //獲取最左邊的1

 for i := 0; i < len(arr); i++ {
  if arr[i]&temp == 0 {  //根據(jù)某一位是否為1進行分組
   right ^= arr[i]
  }
 }
 left = right ^ left
 return left, right
}