題目描述

一個整型數組 nums 里除兩個數字之外，其他數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。要求時間復雜度是 O(n)，空間復雜度是 O(1)。

• 2 <= nums.length <= 10000

題目樣例          

示例

• 輸入：nums = [4,1,4,6]

• 輸出：[1,6] 或 [6,1]

• 輸入：nums = [1,2,10,4,1,4,3,3]

• 輸出：[2,10] 或 [10,2]

題目思考

1. 如果其他數字都出現兩次, 只有一個數字出現一次如何解決?
2. 如何做到空間復雜度是 O(1)?

解決方案

思路

• 分析題目, 相信大家都能想到計數字典的方案, 就是記錄每個數字的次數, 然后找次數為 1 的數字, 但這樣空間復雜度為 O(N), 不滿足要求
• 我們先來分析一個簡化問題:                          如果其他數字都出現兩次, 只有一個數字出現一次如何解決?
• 這個問題估計不少同學都見過, 一個很巧妙的做法是                           異或所有數字, 因為兩個相同數字的異或結果一定為 0, 所以最終異或的結果一定是那個出現一次的數字
• 那針對這道題, 還可以利用異或思路嗎?
• 答案是肯定的, 假設我們還是異或所有數字, 那么                          最終異或出來的值等價于那兩個出現一次的數字的異或結果, 因為其他出現兩次的數字異或都是 0, 對最終異或結果沒有影響.
• 而異或結果中的某一位 1, 代表這兩個數字在這一位上的取值不同, 一個是 0, 一個是 1
• 我們可以利用這一點,                          將原數組分為兩類, 一類是該位為 1 的, 一類是該位為 0 的. 對于出現兩次的數字而言, 它們肯定落在同一類里面; 而對于這兩個出現一次的數字, 它們被分屬在兩個不同類中.
• 這樣問題就轉換成了上面描述的簡化問題, 只需要對這兩類分別求出它們的異或結果, 自然就是對應兩個出現一次的數字了~
• 最后一個問題: 如何求異或結果 xor 的某一位 1 呢?
• 我們可以利用循環, mask 從 1 開始, 判斷 xor 的這一位是否為 1, 是的話就跳出循環, 否則 mask 左移一位, 直到超出 xor
• 當然還有更簡單的做法, 利用樹狀數組的 lowbit, 也即                           xor & -xor, 直接就能求得最低位的 1 對應的數字, 這個大家手動模擬下補碼就知道是為什么了
• 下面代碼對必要的步驟有詳細的解釋, 方便大家理解

復雜度

• 時間復雜度 O(N): 遍歷兩遍數組
• 空間復雜度 O(1): 只使用了幾個變量

代碼

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        # 先拿到所有數字的異或結果, 該結果一定至少有一位是1, 否則就不可能有兩個出現一次的數字
        xor = 0
        for n in nums:
            xor ^= n
        # 然后隨便針對異或結果的某一位1, 將原數組分為兩類, 自然兩個出現一次的數字就會分別落在不同類里面, 否則其異或結果的這一位不可能是1
        # 這里直接利用樹狀數組的lowbit(即原來的數字的最低位的1)
        mask = xor & -xor
        a, b = 0, 0
        for n in nums:
            if n & mask:
                # 如果數字的這一位是1, 歸為一類, 求它們的異或值, 即為其中一個出現一次的數
                a ^= n
            else:
                # 如果數字的這一位是0, 歸為另一類, 求它們的異或值, 即為另一個出現一次的數
                b ^= n
        return [a, b]