建站
咨詢
售后
建站咨詢
新聞中心
前言
上次咱們聊了聊異或運(yùn)算的妙用，其實(shí)簡單來說，就是記住異或運(yùn)算的三個(gè)特性
創(chuàng)新互聯(lián)公司成立與2013年，先為灌云等服務(wù)建站，灌云等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為灌云企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。
- 0和任何數(shù)N進(jìn)行異或運(yùn)算，結(jié)果為N。
- 任何數(shù)N和自己進(jìn)行異或運(yùn)算，結(jié)果為0。
- 異或運(yùn)算滿足交換律和結(jié)合律 當(dāng)然如果您對這幾個(gè)特性不是很了解，或者不是很熟悉異或運(yùn)算的話，建議先看看這篇文章?? 位運(yùn)算的妙用--異或運(yùn)算??。
「閑話不用多說，咱們來看面試真題」
Q1:一個(gè)數(shù)組中有一種數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，怎么找到這一個(gè)數(shù)
「要求：時(shí)間復(fù)雜度O(n)」。
其實(shí)這道題還是比較好理解的。
咱們直接來舉例子。
比如數(shù)組[1,1,2,2,3] 把3找出來即可，因?yàn)?只出現(xiàn)了1次，為奇數(shù)次，其余的數(shù)字出現(xiàn)的都為偶數(shù)次。
比如數(shù)組[1,1,2,2,3,3,3] 同樣把3找出來即可。
其實(shí)最簡單的方法，也就是暴力破解法，咱們可以把數(shù)組循環(huán)一遍，把每個(gè)數(shù)字出現(xiàn)的數(shù)字記錄在另一個(gè)數(shù)組中(需要記錄數(shù)字和該數(shù)字出現(xiàn)的次數(shù)的map)，然后循環(huán)另一個(gè)數(shù)組找出出現(xiàn)次數(shù)為奇數(shù)的即可?！傅沁@個(gè)題目有要求」，時(shí)間復(fù)雜度要求為O(n)，也就是說只能循環(huán)一次就把結(jié)果就找出來，所以暴力破解法肯定是行不通的。所以咱們必須得換個(gè)思路。
利用異或運(yùn)算的規(guī)律來解題
首先，在異或運(yùn)算中「任何數(shù)N和自己進(jìn)行異或運(yùn)算，結(jié)果為0」,所以我們把數(shù)組中的所有數(shù)進(jìn)行異或運(yùn)算，所有「出現(xiàn)偶數(shù)次的數(shù)字進(jìn)行異或運(yùn)算結(jié)果為0」，咱們來看一個(gè)例子(因?yàn)楫惢蜻\(yùn)算滿足交換律，所以不用關(guān)心數(shù)字出現(xiàn)的位置)。
arr = [a,b,b,c,c,c,c,d,d.............]
比如看上述數(shù)組，咱們來對每個(gè)元素進(jìn)行異或運(yùn)算。
temp = a ^ b ^ b ^ c ^ c ^ c ^ c ^ d ^ d
因?yàn)椤溉魏螖?shù)N和自己進(jìn)行異或運(yùn)算，結(jié)果為0」所以除了a以外的數(shù)字，異或結(jié)果為0。
所以全部進(jìn)行異或運(yùn)算一次的結(jié)果為：
temp = a^0
其實(shí)簡單的說就是兩個(gè)b異或結(jié)果為0，兩個(gè)c異或結(jié)果是0(上面的case寫了4個(gè)c，其實(shí)結(jié)果是一樣的)，兩個(gè)d異或結(jié)果為0，那么所有的數(shù)字異或下來，出現(xiàn)偶數(shù)次的結(jié)果異或運(yùn)算的結(jié)果就為0。
另外根據(jù)「0和任何數(shù)N進(jìn)行異或運(yù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默認(rèn)為0 相當(dāng)于0^a(出現(xiàn)奇數(shù)次的數(shù)字)^b^b^c^c.......,根據(jù)上述運(yùn)算的解析，結(jié)果為a，也就是我們想找到的數(shù)
}
return temp
}如果上面的題您已經(jīng)明白了，那么「接下來咱們加大難度，看一種更復(fù)雜的情況」。
Q2:一個(gè)數(shù)組中有兩種數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，怎么找到這一個(gè)數(shù)
「要求：時(shí)間復(fù)雜度O(n)」。
這道題和上面那道題的區(qū)別就在于「有兩種數(shù)字出現(xiàn)了奇數(shù)次」。
arr = [a,b,c,c,d,d,e,e......]
其實(shí)簡單說也就是要把上面數(shù)組arr中的a和b分別找出來，如果按照前面的方法全部異或一次，那么結(jié)果肯定為a^b,我們的目的是把a(bǔ)和b分別找出來，這種辦法當(dāng)然是行不通的，或者說是不夠的。
但是上面計(jì)算之后的結(jié)果：
temp= a^b(其余出現(xiàn)偶數(shù)次的數(shù)字進(jìn)行異或運(yùn)算結(jié)果都為0)
首先，因?yàn)閍和b是兩種數(shù)，所以「a肯定是不等于b的」,所以「a^b的結(jié)果肯定大于0」,換句話說a^b的結(jié)果，也就是「temp的二進(jìn)制表現(xiàn)肯定是至少有一位是1的」。這句話很重要，明白了這句話咱們就繼續(xù)往下看。
比如temp的第7位為1，那就說明a和b的第7位是不一樣的，一個(gè)為0，一個(gè)為1。那么咱們是不是可以通過第7位是否為1，然后進(jìn)行分組，「每個(gè)分組中出現(xiàn)的偶數(shù)次的數(shù)字的異或結(jié)果都是0的」，所以最后兩個(gè)分組各自剩下的就是所需數(shù)字了。
咱們先來看一個(gè)方法。
res := num & (^num + 1)
上述方法的目的是獲取num最左邊的1。什么意思呢?比如num是 1011011，那么他最左邊的1 就是00000001。
咱們用一個(gè)代入的方式一步一步的計(jì)算試試。
所以最后算法如下：
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進(jìn)行分組
right ^= arr[i]
}
}
left = right ^ left
return left, right
} 分享標(biāo)題：位運(yùn)算的秒用--異或運(yùn)算面試真題
標(biāo)題網(wǎng)址：http://www.5511xx.com/article/dpjgiec.html
