###### tags: `Leetcode` `medium` `bit` `python`

# 137. Single Number II

## [題目連結:] https://leetcode.com/problems/single-number-ii/

## 題目:
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

## 解題想法:
兄弟題目:[136. Single Number](/3ue4FsPDReW3k8lZ7plVoQ)

* 此題為給一數組，裡面元素只有一個是單獨的，其他都剛好三個，找出單獨的元素。
* 要求linear runtime complexity
* use only constant extra space
* 利用bit:
* 將32位的二進制數每一位都進行遍歷
* 統計數組中每個數字對於二進位每個位置出現的和
* 因為每個數子出現3or1次
* 若32bit中某位出現次數不是3次，表示該位置為單獨的該數導致

## Python:

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = 0
        #check:2^0~ 2^31  即32bit
        for i in range(32):
            count=0
            mask=1<<i
            #對於所有num轉成2進制並按照位置累加所有位元
            for num in nums:
                if (num&mask)!=0:
                    count+=1
            #若正常出現3次 則進不去此if
            if (count%3)==1:
                ans = ans|mask
                
        #怕為負數時候 2**31的表達需要改
        if ans>=2**31:
            ans-=2**32
        return ans
        
nums = [-2,-2,1,1,4,1,4,4,-4,-2]
result = Solution()
ans = result.singleNumber(nums)
print(ans)