LeetCode-137. 只出现一次的数字 II【位运算 数组】
- 题目描述：
- 解题思路一：
- 解题思路二：符号位一起判断。背诵版
- 解题思路三：0
题目描述：
给你一个整数数组 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 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
解题思路一：
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for i in range(31):
cnt1 = sum(x >> i & 1 for x in nums)
ans |= cnt1 % 3 << i
# 最高位是符号位，下面这行相当于统计负数的个数
cnt1 = sum(x >> 31 & 1 for x in nums)
# 如果 cnt1 % 3 == 1，那么答案的最高位是 1，否则是 0
# Python 只能通过减法把最高位置为 1
return ans - (cnt1 % 3 << 31)
时间复杂度：O(n)
空间复杂度：O(1)
解题思路二：符号位一起判断。背诵版
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for i in range(32):
total = sum((num >> i) & 1 for num in nums)
if total % 3:
if i == 31:
ans -= (1 << i)
else:
ans |= (1 << i)
return ans
时间复杂度：O(n)
空间复杂度：O(1)
解题思路三：0
时间复杂度：O(n)
空间复杂度：O(n)
♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠
