c++怎么判斷只出現(xiàn)一次的數(shù)字

本篇內(nèi)容主要講解“c++怎么判斷只出現(xiàn)一次的數(shù)字”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“c++怎么判斷只出現(xiàn)一次的數(shù)字”吧!

算法

位運算異或的使用(一)中，兩位相同的數(shù)異或為0，轉(zhuǎn)換成3位數(shù)的"異或"操作位0，也就是說我們需要實現(xiàn)同一個bit位的3個1，操作為0就可以，將問題轉(zhuǎn)換為對如何實現(xiàn)同一bit位的三個數(shù)的操作a?b?c =0的運算。

因為兩位數(shù)的異或操作，是同一個bit位的兩個數(shù)的加法，忽略進位的情況，換種說法就是兩數(shù)相加對2取余數(shù)。所以三個相同的數(shù)的a?b?c = 0的操作就變成了，三位數(shù)操作對3取余了。同樣的道理，4位數(shù),n位數(shù)都可以采用這一個算法來實現(xiàn)。

題目:只出現(xiàn)一次的數(shù)字

算法1:數(shù)學(xué)公式

這個題目可以轉(zhuǎn)換成下面的公式：2c = 3(a+b+c)-sum,

這里的a,b,c是數(shù)組中出現(xiàn)的元素，c是出現(xiàn)了一次的數(shù)，a,b都是出現(xiàn)了3次的數(shù)。

sum表示的是：數(shù)組里面所有數(shù)的和。

備注：同樣的算法，也適合數(shù)組里面有n次重復(fù)的數(shù)組，和1個不重復(fù)的數(shù) ，公式為：n(a+b+c)-sum = (n-1)c

代碼實現(xiàn)：

func singleNumber(nums []int) int {    m := make(map[int]int)     s1,s2 := 0,0    for _,n:=range nums {        _,ok := m[n]        if !ok {            m[n] = n        }        s1 += n    }       for _,v:= range m {        s2 += v    }    res := (3*s2-s1)/2    return res}// 算法：假設(shè)3個a,b,一個c: 公式： 3(a+b+c) - sum = 2c

算法2: 采用位運算

指導(dǎo)思路是：轉(zhuǎn)換成前面算法篇：位運算異或的使用(一)中，兩位相同的數(shù)異或為0，轉(zhuǎn)換成3位數(shù)的"異或"操作位0，也就是說我們需要實現(xiàn)同一個bit位的3個1，操作為0就可以，將問題轉(zhuǎn)換為對如何實現(xiàn)同一bit位的三個數(shù)的操作a?b?c =0的運算。

因為兩位數(shù)的操作采用的是異或，也就是 ：

1^1 = 0 1^0 = 10^1 = 10^0 =0這其實是同一個bit位的兩個數(shù)的加法，忽略進位的情況，換種說法就是兩數(shù)相加對2取余數(shù)。

所以三個相同的數(shù)的a?b?c = 0的操作就變成了，三位數(shù)操作對3取余了。

代碼實現(xiàn)：

func singleNumber(nums []int) int {    num,res := 0,0    for i:=0;i<64;i++ {        // 每一bit位都需要計算，所以這里要做清0處理        num = 0        for _, n := range nums {            // 通過右移，來計算num的數(shù)量            num += (n>>i)&1        }        // 將計算結(jié)果還原到對應(yīng)的bit位        res |= (num)%3<<i    }    return res}

到此，相信大家對“c++怎么判斷只出現(xiàn)一次的數(shù)字”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！