LeetCode如何求數(shù)組中數(shù)字出現(xiàn)的次數(shù)

題目描述

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

• 1 <= nums.length <= 10000
• 1 <= nums[i] < 2^31

題目樣例

示例

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

• 輸出：4

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

• 輸出：1

題目思考

1. 還能使用昨天的異或思路嗎?
2. 可以單獨(dú)統(tǒng)計(jì)每一位嗎?

解決方案

思路

• 分析題目, 其他數(shù)字都出現(xiàn)了三次, 這時(shí)候如果還用異或的話, 這些出現(xiàn) 3 次的數(shù)字并不能異或?yàn)?0, 而是異或成各自自身, 最終異或的結(jié)果相當(dāng)于每個(gè)不同的數(shù)都異或了一次, 沒有任何意義
• 換個(gè)角度分析, 如果我們 單獨(dú)統(tǒng)計(jì)每個(gè)數(shù)字二進(jìn)制每一位上為 1 的次數(shù)并累加, 那么對(duì)于出現(xiàn) 3 次的數(shù)而言, 它們的這一位為 1 的次數(shù)之和一定是 3 的倍數(shù)
• 很顯然, 加上了單獨(dú)出現(xiàn) 1 次的數(shù)之后, 這一位上的次數(shù)除以 3 的余數(shù)要么是 0 (代表這個(gè)數(shù)字這一位是 0), 要么是 1(代表這個(gè)數(shù)字這一位是 1), 利用這一點(diǎn), 我們就能計(jì)算出這個(gè)數(shù)字每一位上到底是 0 還是 1
• 看到這里, 結(jié)合昨天的                    劍指 Offer 56 - I. 數(shù)組中數(shù)字出現(xiàn)的次數(shù) - leetcode 劍指 offer 系列, 相信聰明的大家都能發(fā)現(xiàn)一些規(guī)律, 我在這里也總結(jié)一下:
• 其他數(shù)字出現(xiàn)                     偶數(shù)次, 某個(gè)數(shù)字出現(xiàn)奇數(shù)次: 全部數(shù)字異或
• 其他數(shù)字出現(xiàn)                     偶數(shù)次, 某兩個(gè)數(shù)字各出現(xiàn)奇數(shù)次: 異或后根據(jù)異或結(jié)果的某個(gè) 1 分兩類
• 其他數(shù)字出現(xiàn)                     奇數(shù)次, 某個(gè)數(shù)字出現(xiàn) 1 次: 按照二進(jìn)制每一位統(tǒng)計(jì)次數(shù), 然后對(duì)這個(gè)奇數(shù)次取模
• 下面代碼對(duì)必要的步驟有詳細(xì)的解釋, 方便大家理解

復(fù)雜度

• 時(shí)間復(fù)雜度 O(N): 遍歷一遍數(shù)組, 然后對(duì)于每個(gè)數(shù)要統(tǒng)計(jì)其每一位的次數(shù), 這部分操作是 O(32) == O(1), 所以總體復(fù)雜度仍為 O(N)
• 空間復(fù)雜度 O(1): 只使用了幾個(gè)變量

代碼

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in range(32):
            # 當(dāng)前統(tǒng)計(jì)的位數(shù)為第i位
            # 假設(shè)i==1, 對(duì)應(yīng)的mask就是0b000...00010 (共32位, 高位全為0)
            mask = 1 << i
            cnt = 0
            for x in nums:
                if x & mask:
                    # 如果這個(gè)數(shù)字與mask相與的結(jié)果為1, 則說明其當(dāng)前位為1, 累加到次數(shù)中
                    cnt += 1
            if cnt % 3 == 1:
                # 如果次數(shù)為1, 則說明出現(xiàn)一次的數(shù)字在這一位上為1, 將最終結(jié)果或上當(dāng)前mask即可
                res |= mask
                # 當(dāng)然也可以選擇結(jié)果加上mask, 因?yàn)槊總€(gè)mask都是只有一位為1且各不相同
                # res += mask
        return res