服装服饰设计网站网站维护年费

题目-中等难度

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. 位运算

class Solution:def singleNumber(self, nums: List[int]) -> int:# 初始化32位计数器counts = [0] * 32# 遍历数组中的每个数字for num in nums:for i in range(32):# 统计第i位的1的个数counts[i] += (num >> i) & 1# 还原结果res = 0for i in range(32):# 只保留模3后剩余的位res |= (counts[i] % 3) << i# 处理符号位（第31位为符号位）if res >= 2**31:res -= 2**32return res

2. 位运算

class Solution:def singleNumber(self, nums: List[int]) -> int:ones, twos = 0, 0for num in nums:# 更新 ones 和 twos# 将当前数字 num 的每一位与 ones 的当前位进行异或操作，并用~two清除那些已经被记录为两次的位ones = (ones ^ num) & ~twos# 将当前数字 num 的每一位与 twos 的当前位进行异或操作，并用~one清除那些已经被记录为一次的位twos = (twos ^ num) & ~onesreturn ones