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

Providence Doucet on Unsplash

題目敘述 Single Number III

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

請找出這兩個烙單的數字。

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

測試範例

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.
3和5就是烙單，只有出現一次的數字。

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

約束條件

Constraints:

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

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

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

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

• Each integer in nums will appear twice, only two integers will appear once.

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

觀察

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

演算法 二進位操作

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

可以怎麼做呢?

兩個烙單的數字代表兩個相異的數字，都只出現一次。

那麼，可以先找出兩個烙單數字相異的bit作為遮罩，
再用XOR過濾掉剩餘都出現兩次的數字(A XOR A = 0)，
最後留下來的數字，恰好就是那兩個烙單的數字。

程式碼 二進位操作

from functools import reduce

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        
        
        xor = lambda x,y : x^y
        
        xor_result = reduce( xor, nums)
        
        # mask is the right-most 1 of xor result
        # use mask to separate nums into two groups, one group contains single_num_a, the other contains single_num_b
        mask = xor_result & -xor_result
        
        single_num_a, single_num_b = 0, 0
        
        for number in nums:
            # separate and collect these two single numbers by masking
            
            if mask&number:
                single_num_a ^= number
            else:
                single_num_b ^= number
                
        return [single_num_a, single_num_b]

複雜度分析

時間複雜度:O(n)

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

空間複雜度: O(1)

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

Reference

[1] Single Number III - LeetCode