剑指Offer56-II-数组中数字出现的次数II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
限制：
-
1 <= nums.length <= 10000
-
1 <= nums[i] < 2^31
来源：力扣（LeetCode）
链接：力扣
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一解
使用位运算，由于“除一个数字只出现一次之外，其他数字都出现了三次”，因此对所有数字的某一位进行求和，其结果是 3 或者 1 或者 0 ，对其 % 3，必然是 0 或者 1 。
1 % 3 = 1
res = 1
3 % 3 = 0
res = 10
3 % 3 = 0
res = 100
class Solution:
def singleNumber(self, nums: List[int]) -> int:
bit_mask = 1 << 31
res = 0
for j in range(32):
bit_sum = 0
for num in nums:
if bit_mask & num: bit_sum += 1
res = (res<<1) + bit_sum%3
bit_mask >>= 1
return res
-
时间复杂度：O(n)
-
空间复杂度：O(1)