動機

是誰想到用bit去統計的

Problem

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,3,2]Output: 3

Example 2:

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

 

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • Each element in nums appears exactly three times except for one element which appears once.

Sol

記下每位位元的1出現幾次，如果到了三次就要把前面的劃掉

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        one = two = three = 0
        for n in nums:
            two = two | (one & n)
            one = one ^ n
            three = one & two
            one = one & ~three
            two = two & ~three
        return one