golang中怎么利用leetcode求數(shù)組中數(shù)字出現(xiàn)的次數(shù)

本篇文章為大家展示了golang中怎么利用leetcode求數(shù)組中數(shù)字出現(xiàn)的次數(shù) ，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

在一個(gè)數(shù)組 nums 中除一個(gè)數(shù)字只出現(xiàn)一次之外，其他數(shù)字都出現(xiàn)了三次。請(qǐng)找出那個(gè)只出現(xiàn)一次的數(shù)字。

示例 1：

輸入：nums = [3,4,3,3]

輸出：4

示例 2：

輸入：nums = [9,1,7,9,7,9,7]

輸出：1

限制：

1 <= nums.length <= 10000

1 <= nums[i] < 2^31

解題思路：

1，首先想到的是map計(jì)數(shù)，顯然不是最優(yōu)的

2，本題的特點(diǎn)，只有一個(gè)只出現(xiàn)了一次，且這個(gè)整數(shù)，只有31位

3，我們統(tǒng)計(jì)整個(gè)數(shù)組中，1到31位，1的個(gè)數(shù)，如果mod 3 不是0 說明只出現(xiàn)一次的數(shù)據(jù)，這一位非零

4，我們將所有非零位組合起來(lái)，就是我們所需要的數(shù)據(jù)

代碼實(shí)現(xiàn)

func singleNumber(nums []int) int {    res:=0    for i:=0;i<32;i++{        count:=0        for _,n:=range nums{            if 1<<i&n>0{                count++            }        }        if count%3!=0{           res|=1<<i        }    }    return res}

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。你可以不使用額外空間來(lái)實(shí)現(xiàn)嗎？

示例 1:

輸入: [2,2,1]

輸出: 1

示例 2:

輸入: [4,1,2,1,2]

輸出: 4

解題思路

異或的性質(zhì)

兩個(gè)數(shù)字異或的結(jié)果a^b是將 a 和 b 的二進(jìn)制每一位進(jìn)行運(yùn)算，得出的數(shù)字。運(yùn)算的邏輯是

如果同一位的數(shù)字相同則為 0，不同則為 1

異或的規(guī)律

任何數(shù)和本身異或則為0

任何數(shù)和 0 異或是本身

代碼實(shí)現(xiàn)

func singleNumber(nums []int) int {    res:=0    for _,n:=range nums{        res^=n    }    return res}

給定一個(gè)整數(shù)數(shù)組 nums，其中恰好有兩個(gè)元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次。找出只出現(xiàn)一次的那兩個(gè)元素。

示例 :

輸入: [1,2,1,3,2,5]

輸出: [3,5]

注意：

結(jié)果輸出的順序并不重要，對(duì)于上面的例子， [5, 3] 也是正確答案。

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。你能否僅使用常數(shù)空間復(fù)雜度來(lái)實(shí)現(xiàn)？

解題思路

異或的規(guī)律中有一個(gè)任何數(shù)和本身異或則為0， 因此我們的思路是能不能將這兩個(gè)不同的數(shù)字分成兩組 A 和 B。

分組需要滿足兩個(gè)條件.

兩個(gè)獨(dú)特的的數(shù)字分成不同組

相同的數(shù)字分成相同組

這樣每一組的數(shù)據(jù)進(jìn)行異或即可得到那兩個(gè)數(shù)字。

問題的關(guān)鍵點(diǎn)是我們?cè)趺催M(jìn)行分組呢？

由于異或的性質(zhì)是，同一位相同則為 0，不同則為 1. 我們將所有數(shù)字異或的結(jié)果一定不是 0，也就是說至少有一位是 1.

我們隨便取一個(gè)， 分組的依據(jù)就來(lái)了， 就是你取的那一位是 0 分成 1 組，那一位是 1 的分成一組。

這樣肯定能保證2. 相同的數(shù)字分成相同組, 不同的數(shù)字會(huì)被分成不同組么。很明顯當(dāng)然可以， 因此我們選擇是 1，也就是

說兩個(gè)獨(dú)特的的數(shù)字在那一位一定是不同的，因此兩個(gè)獨(dú)特元素一定會(huì)被分成不同組

代碼實(shí)現(xiàn)

func singleNumber(nums []int) []int {    s:=0    for _,n:=range nums{        s^=n    }    l:=s&(-s)    //fmt.Println(s,l)    var z1,z2 int    for _,n:=range nums{       if l&n==l{        z1^=n       }else{          z2^=n       }    }    return []int{z1,z2}}
/*思路: 只有兩個(gè)元素出現(xiàn)一次,其它的元素都出現(xiàn)兩次.
1,全部元素異或消掉出現(xiàn)兩次的數(shù)字. 異或的結(jié)果為s.
2,尋找s的lowbit值. lowbit(s)為s的二進(jìn)制表達(dá)式中最右邊的1所對(duì)應(yīng)的值. 因此lowbit(s)二進(jìn)制表達(dá)式中只有一個(gè)bit 1.
lowbit(s) = s & -s
例如: s=1010
lowbit(s) = 1010 & 0110 = 0010 = 2
3,用lowbit(s)將數(shù)組分成兩組. 一組中,元素A[i] & lowbit(s) == lowbit(s), 即包含lowbit(s)的bit 1. 剩余的是另一組.
而且,兩個(gè)不同數(shù)也一定分在不同組. 因?yàn)楫惢蛑祍中的bit1就是因?yàn)閮蓚€(gè)數(shù)字的不同而貢獻(xiàn)的.
4,同一組的元素再異或求出不同數(shù)字. 出現(xiàn)兩次的數(shù)字, 肯定出現(xiàn)同一組, 異或后消除掉.*/

上述內(nèi)容就是golang中怎么利用leetcode求數(shù)組中數(shù)字出現(xiàn)的次數(shù) ，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注億速云行業(yè)資訊頻道。