動機

又是看創意的一題，以後是不是要給這種題目個標籤

用mask其中一個bit做分類依據

Problem

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

 

Example 1:

Input: nums = [1,2,1,3,2,5]Output: [3,5]Explanation:  [5, 3] is also a valid answer.

Example 2:

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

Example 3:

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

 

Constraints:

    t
  • 2 <= nums.length <= 3 * 104
    • t
  • -231 <= nums[i] <= 231 - 1
    • t
  • Each integer in nums will appear twice, only two integers will appear once.

Sol

用xor一次後，會拿到兩個數字的xor，之後我們取其中一個bit，做分類的mask

重複兩次的數字一定往其中一邊走，而不同的數字因為mask，一定不會走向同一個地方

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        mask = reduce(lambda acc,n: acc^n,nums,0)
        mask = mask & -mask #only keep LSB of mask
        ret = [0,0]
        for n in nums:
            if n & mask:
                ret[0] = ret[0] ^ n
            else:
                ret[1] = ret[1] ^ n
        return ret