題目描述

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

• 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. 可以單獨統計每一位嗎?

解決方案

思路

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

復雜度

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

代碼

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