【LeetCode】136. 隻出現一次的數字（異或運算秒殺）& 137. 隻出現一次的數字 II

類似運算技巧的題目：​​判斷一個數是不是2的整數次幂(兩種方法)​​.

136. 隻出現一次的數字

1. 題目描述

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

說明：

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

示例 1:

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

示例 2:

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

2. 思路

第一時間想到的是 哈希表，但是哈希表需要 O(n) 的空間。要達到 O(1) 的空間，采樣 異或運算 ^

99 ^ 99 == 0
99 ^ 0 == 0
99 ^ 19 == 112      

1. 異或運算了解角度 a

a 和 b 均為 0 或者1 （二進制）

1. 當 a、b值相同時，異或結果為 0
2. 當 a、b值不同時，異或結果為 1

2. 異或運算了解角度 b

可以了解為不進位的加法

0 ^ 0 == 0

0 ^ 1 == 1

1 ^ 0 == 1

1 ^ 1 == （1）0

3. 異或運算了解角度 c

滿足結合律和配置設定律

1. a ⊕ a = 0
2. a ⊕ b = b ⊕ a
3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;
4. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c.
5. a ⊕ b ⊕ a = b.

4. 結合本題

a ^ 0 = a ( 和 0 異或運算得到本身)

簡單假設數組中數為：

nums = [5, 6, 6, 7, 7, 8, 8]
則 5 ^  6 ^ 6  ^  7 ^7  ^  8 ^ 8 
 = 5 ^ (6 ^ 6) ^ (7 ^7) ^ (8 ^ 8) 
 = 5 ^ 0 ^ 0 ^ 0
 = 5 ^ 0
 = 5      

即把 nums 中所有元素一起異或運算得到隻出現一次的那個數字

3. 代碼

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for num in nums:
            res = res ^ num
        return      

複雜度分析

• 時間複雜度：O(n)，其中 n 是數組長度。隻需要對數組周遊一次。
• 空間複雜度：O(1)。

參考：

1. ​​LeetCode官方題解​​

==========================================================================================================================

137. 隻出現一次的數字 II

一、題目描述

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

說明：

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

示例 1:

輸入: [2,2,3,2]
輸出: 3      

示例 2:

輸入: [0,1,0,1,0,1,99]
輸出: 99      

二、解題思路 & 代碼

2.1 HashMap

周遊輸入數組，統計每個數字出現的次數，最後傳回出現次數為 1 的數字。

from collections import Counter
class Solution:
    def singleNumber(self, nums):
        hashmap = Counter(nums)
            
        for key in hashmap.keys():
            if hashmap[key] == 1:
                return      

2.2 HashSet

将輸入數組存儲到 HashSet，然後使用 HashSet 中數字和的三倍與數組之和比較。

class Solution:
    def singleNumber(self, nums):
        return (3 * sum(set(nums)) - sum(nums)) // 2      

複雜度分析

• 時間複雜度：，周遊輸入數組。
• 空間複雜度：，存儲

2.3 位運算

解題思路：

如下圖所示，考慮數字的二進制形式，對于出現三次的數字，各 二進制位 出現的次數都是 ​

​3​

​ 的倍數。

是以，統計所有數字的各二進制位中 ​

​1​

​​ 的出現次數，并對 ​

​3​

​ 求餘，結果則為隻出現一次的數字。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        b1,b2 = 0,0#出現一次的位，和兩次的位
        for n in nums:
            b1 = (b1 ^ n) & ~ b2 #既不在出現一次的b1，也不在出現兩次的b2裡面，我們就記錄下來，出現了一次，再次出現則會抵消
            b2 = (b2 ^ n) & ~ b1 #既不在出現兩次的b2裡面，也不再出現一次的b1裡面(不止一次了)，記錄出現兩次，第三次則會抵消
        return      

• 時間複雜度：，周遊輸入數組。
• 空間複雜度：，不使用額外空間。

參考：

1. ​​LeetCode官方題解​​
2. ​​LeetCode優秀題解​​