萬綠叢中一點紅 落單的數字II 有教學影片_Single Number II_二進位操作_Leetcode #260

Edward Howell on Unsplash

題目敘述 Single Number II

給定一個輸入陣列，已知有一個烙單的數字，其他剩餘的數字都恰巧出現三次。

請找出這個烙單的數字。

題目額外提出限制，請使用O(n)線性時間、O(1)常數空間複雜度的演算法。

測試範例

Example 1:

Input: nums = [2,2,3,2]
Output: 3
3是烙單的數字，只出現一次。

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99
99是烙單的數字，只出現一次。

約束條件

Constraints:

• 1 <= nums.length <= 3 * 10^4

輸入陣列的長度介於1~三萬之間。

• -2^31 <= nums[i] <= 2^31 - 1

每個陣列元素都在4byte整數範圍內。

• Each element in nums appears exactly three times except for one element which appears once.

只有恰好一個數字烙單，其他剩餘的數字都剛好出現三次。

觀察

如果最直覺的想法，就是用字典去記錄每個數字的出現次數。
找出出現次數只有一次的數字即可。

演算法 二進位操作 + 狀態機

但是，困難點在於題目多了額外拘束，限定使用O(1)常數空間。

可以怎麼做呢?

教學影片

可以用State machine維持一個有限狀態機，分別記錄出現零次(等價於 mod 3 餘零)、一次、兩次的數字，並且用布林代數推導狀態更新公式。

其他的數字都會回到 mod 3餘零的狀態，只有落單的數字會停留在出現一次的狀態。

最後，留在出現一次的那個數字就是最終答案，也就是落單的數字。

程式碼 二進位操作+ 狀態機

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        state_one = 0
        state_two = 0

        for num in nums:

            state_one = (num ^ state_one) & ~state_two
            state_two = (num ^ state_two) & ~state_one

        return state_one

複雜度分析

時間複雜度:O(n)

從左到右，掃描每個數字，每個數字計算一次。

空間複雜度: O(1)

使用到的都是固定尺寸的臨時變數，為常數級別O(1)。

關鍵知識點

這個系列題考點在於二進位操作、XOR運算子特性、布林代數的化簡。

強烈讀者建議一起複習。

二進位操作 尋找落單的數字 Single Number Leetcode #136 精選75題

萬綠叢中一點紅 落單的數字 Single Number III_二進位操作_Leetcode #260

Reference

[1] Single Number II - LeetCode