golang中怎么利用leetcode求數組中數字出現的次數

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

在一個數組 nums 中除一個數字只出現一次之外，其他數字都出現了三次。請找出那個只出現一次的數字。

示例 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計數，顯然不是最優的

2，本題的特點，只有一個只出現了一次，且這個整數，只有31位

3，我們統計整個數組中，1到31位，1的個數，如果mod 3 不是0 說明只出現一次的數據，這一位非零

4，我們將所有非零位組合起來，就是我們所需要的數據

代碼實現

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}

給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。

說明：

你的算法應該具有線性時間復雜度。你可以不使用額外空間來實現嗎？

示例 1:

輸入: [2,2,1]

輸出: 1

示例 2:

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

輸出: 4

解題思路

異或的性質

兩個數字異或的結果a^b是將 a 和 b 的二進制每一位進行運算，得出的數字。運算的邏輯是

如果同一位的數字相同則為 0，不同則為 1

異或的規律

任何數和本身異或則為0

任何數和 0 異或是本身

代碼實現

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

給定一個整數數組 nums，其中恰好有兩個元素只出現一次，其余所有元素均出現兩次。找出只出現一次的那兩個元素。

示例 :

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

輸出: [3,5]

注意：

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

你的算法應該具有線性時間復雜度。你能否僅使用常數空間復雜度來實現？

解題思路

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

分組需要滿足兩個條件.

兩個獨特的的數字分成不同組

相同的數字分成相同組

這樣每一組的數據進行異或即可得到那兩個數字。

問題的關鍵點是我們怎么進行分組呢？

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

我們隨便取一個， 分組的依據就來了， 就是你取的那一位是 0 分成 1 組，那一位是 1 的分成一組。

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

說兩個獨特的的數字在那一位一定是不同的，因此兩個獨特元素一定會被分成不同組

代碼實現

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}}
/*思路: 只有兩個元素出現一次,其它的元素都出現兩次.
1,全部元素異或消掉出現兩次的數字. 異或的結果為s.
2,尋找s的lowbit值. lowbit(s)為s的二進制表達式中最右邊的1所對應的值. 因此lowbit(s)二進制表達式中只有一個bit 1.
lowbit(s) = s & -s
例如: s=1010
lowbit(s) = 1010 & 0110 = 0010 = 2
3,用lowbit(s)將數組分成兩組. 一組中,元素A[i] & lowbit(s) == lowbit(s), 即包含lowbit(s)的bit 1. 剩余的是另一組.
而且,兩個不同數也一定分在不同組. 因為異或值s中的bit1就是因為兩個數字的不同而貢獻的.
4,同一組的元素再異或求出不同數字. 出現兩次的數字, 肯定出現同一組, 異或后消除掉.*/

上述內容就是golang中怎么利用leetcode求數組中數字出現的次數 ，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。