LeetCode 面試題56 – I. 數組中數字出現的次數 | Python

• 2020 年 4 月 29 日
• 筆記

面試題56 – I. 數組中數字出現的次數

題目

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

示例 1：

輸入：nums = [4,1,4,6]
輸出：[1,6] 或 [6,1]

示例 2：

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

限制：

• 2 <= nums <= 10000

解題思路

思路：異或，位運算

先說下異或的性質：二進制位同一位相同則為 0，不同則為 1。

再說說一下異或的規律：

• 若兩數值相同，兩者的異或結果為 0，（即是任何數與自身異或結果為 0）
• 任何數與 0 異或結果為本身

同時異或是滿足交換律，結合律的（數學符合：⊕）

• 交換律： a ⊕ b = b ⊕ a
• 結合律： a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c

回來看本題，題目說明，【整型數組 nums 中，除兩個數字之外，其他數字都出現了兩次】。那麼根據交換律、結合律將相同數字進行異或運算，那麼相同數字都會變為 0，再根據第二條規律，那麼剩下的出現一次的數字。

在這裡主要需要實現的如何確保將數組分成兩組，使得：

• 只出現一次的數字，在不同的兩組；
• 相同的數組出現在相同的組。

只有這樣，每組進行異或運算的時候，最終才會剩下單獨的數字。那麼該如何進行分組？特別是如何將兩個不同的數字分到不同的組？

具體實現代碼如下。

代碼實現

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        res = 0
        # 全員進行異或
        for num in nums:
            res ^= num
        
        # 找出不為 0 的最低位
        # & 位運算的使用
        div = 1
        while (div & res == 0):
            div <<= 1
        
        # 進行分組
        p, q = 0, 0
        for num in nums:
            if num & div:
                p ^= num
            else:
                q ^= num
            
        return [p, q]

實現結果

以上就是使用異或，位運算的思路，解決《面試題56 – I. 數組中數字出現的次數》問題的主要內容，題目主要的難度在於如何對數組進行分組，然後根據異或的規律性質進行求解。

歡迎關注微信公眾號《書所集錄》