- JY：找出列表中只出现 1 次的数值（其它数值均出现 3 次）
- 参考：https://www.yuque.com/it-coach/leetcode/xkogct
1、利用数值二进制位的特性（执行效率并不高）
- 题目中明确了数字的范围是 32 位整型（
-2^31 <= nums[i] <= 2^31 - 1），所以从低位遍历到高位，将所有数字的二进制对应位相加，由于除了一个数字外其余数字都出现了 3 次，故所有数字的同一个二进制位之和与 3 求余所得数就是目标数字对应所在位的二进制。 - 时间复杂度
O(n * logC)
-
n是数组的长度，C是元素的数据范围- 本题中
log C = log 2^32 = 32（需遍历第 0 - 31 个二进制位）
- 空间复杂度
O(1)
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
# jy: 记录目标数值的二进制表示形式
bin_num = ""
# jy: 数值总共有 32 个二进制位 (包含最高位的符号位)
for i in range(32):
# jy: 统计所有数值的第 i 位上的二进制数之和
sum_ = 0
for num in nums:
# jy: 右移 i 位后 (最开始 i 为 0) 并和 1 进行与运算即可获
# 取 num 的二进制形式的第 i 位 (最低位为第 0 位) 的数值
# jy: 注意: 负数的最高位数值位为 1
sum_ += ((num >> i) & 1)
# jy: 构造目标数值的二进制表示形式
bin_num = str(sum_ % 3) + bin_num
# jy: 如果所有数值的第 i 位的数值之和与 3 求余数为 1, 表明目标
# 数值的第 i 位为 1, 此时将 1 左移 i 位后 (即 2 ** i) 加上
# 上一轮 result 结果 (即之前的二进制位对应的数值结果)
if sum_ % 3 == 1:
# jy: 最高位符号位 (i == 31) 为 1 时, 需进行特殊处理: 因为计算机
# 中数值是以补码的形式存储, 因此不能直接 ``result = -result``,
# 以 -4 为例:
# 原码: 10000000000000000000000000000100
# 反码: 11111111111111111111111111111011
# 补码: 11111111111111111111111111111100
# 此时 ``result - 2 ** 31`` 才是目标数值 -4
if i == 31:
# jy: 1 << 31 表示 1 左移 31 位 (即 2 ** 31)
result -= (1 << 31)
else:
# jy: 以下两个语句等价 (注意: 只有当 result 对应的数值
# 与 1 << i 对应的数值的二进制形式没有重叠的值为 1
# 的位时才能采用下面的第一种写法)
result |= 1 << i
#result += 1 << i
# jy: 查看目标数值的二进制表示形式; 可发现, 数值的二进制形式是以补码的形式在计算机中体现;
# (正数的补码为其原码本身, 负数的补码为: 除符号位外的原码的反码 + 1); 如 -4:
# 原码: 10000000000000000000000000000100
# 反码: 11111111111111111111111111111011
# 补码: 11111111111111111111111111111100
print(bin_num)
return result
nums = [-4]
res = Solution().singleNumber(nums)
# jy: -4
print(res)2、改写解法 1
- 用一个长度为 32 的列表记录目标数值的每一个二进制位
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ls_bit = [0] * 32
# jy: 将所有数值的每一个二进制位的数值均相加求和
for num in nums:
for j in range(32):
ls_bit[j] += num & 1
num >>= 1
result, m = 0, 3
# jy: 从最高位 (第 31 位) 开始, 不断补齐目标数值的二进制位
# jy: 如果目标值为 -4, 则:
# 1) 以下 for 循环结束后得到的 result 为:
# 11111111 11111111 11111111 11111100
# 2) 与 0xffffffff 进行异或运算后结果为 (即为 3):
# 00000000 00000000 00000000 00000011
# 3) ~3 的结果 (即补码的形式) 即为 -4
for i in range(32):
result <<= 1
# jy: ls_bit[31 - i] % m 得到的结果即目标数值在第 31-i
# 位的二进制结果值 (二进制的最右侧为第 0 位)
result |= ls_bit[31 - i] % m
return result if ls_bit[31] % m == 0 else ~(result ^ 0xffffffff)
nums = [2, 2, 3, 2]
res = Solution().singleNumber_v2(nums)
# jy: 3
print(res)3、改写解法 1
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
result = 0
for i in range(32):
sum_ = sum((num >> i) & 1 for num in nums)
if sum_ % 3:
if i == 31:
result -= (1 << i)
else:
#result += 1 << i
result |= (1 << i)
return result
nums = [0, 1, 0, 1, 0, 1, 99]
res = Solution().singleNumber(nums)
# jy: 99
print(res)4、有限状态自动机（性能优）
- 时间复杂度
O(n)
-
- 遍历数组占用
O(n) - 每轮中的常数个位运算操作占用
O(32 * 3 * 2) = O(1)
- 遍历数组占用
- 空间复杂度
O(1)
- 各二进制位的位运算规则相同 ，因此只需考虑一位即可。
- 所有数值的指定二进制位中 1 的个数除 3 求余数有 3 种结果：0、1、2（尽管其它数都出现 3 次，但遍历时是逐个遍历，当第二次遍历相同数值时，就可能存在余数为 2 的情况）。对应的状态转换规则如下：
-
- 余数的三种结果（对应三种状态）：0、1、2
- 若输入位为 0，则状态保持不变
- 若输入位为 1，则转至下一个状态
- 由于一个二进制位只能表示 0、1 两种状态，因此需使用两个二进制位来表示 3 个状态（用 0、1、2 对应的二进制形式即可），因此状态转换变为：
00 → 01 → 10 → 00 → ⋯
- 记两位分别为
two one（状态的两个二进制位） - 接下来需通过状态转换表推导出状态转换的计算公式。
- 位运算回顾（以下的
x为二进制数值 0 或 1）：
-
- 异或运算：
x ^ 0 = x，x ^ 1 = ~x - 与运算：
x & 0 = 0，x & 1 = x
- 异或运算：
- 状态转换表（设当前状态为
two one，输入二进制位n）：
（1）计算one的方法（状态转换计算公式）
- 以下是结合当前
n，在原two的基础上计算one
- 难点：需逐步理解以上不同情况下
one的计算（异或运算、与运算），以及两者的整合过程；可参考以下代码逻辑进行理解（one的计算方法）：
# jy: 最朴素的拆分计算方法:
if two == 0:
if n == 0:
one = one
if n == 1:
one = ~one
if two == 1:
one = 0
# jy: 使用异或运算将以上拆分简化:
if two == 0:
one = one ^ n
if two == 1:
one = 0
# jy: 使用与运算可继续简化为:
one = one ^ n & ~two（2）计算two的方法
- 由于先计算
one，因此应在新one的基础上计算two - 因此，在新
one的基础上，结合当前n，计算two（根据状态转换表进行推导计算）
-
- 当新
one为 0 时：
- 当新
-
-
- 当
n == 0：two = two - 当
n == 1：two = ~two
- 当
-
-
- 当新
one为 1 时：two = 0 - 因此，可以用相同的公式计算
two：two = two ^ n & ~one
- 当新
- 修改为新
one后，得到了新的状态图【以下新状态图的转换比较抽象，参考以上理解过程进行理解即可】：
- 因此可使用同样的方法计算
two：
two = two ^ n & ~one- 返回值：
-
- 以上是对数值二进制位中的 1 位的分析，而 int 类型的 32 位具有相同的运算规则，因此可将以上公式直接套用在 32 位上。
-
- 遍历完所有数字后，各二进制位都处于状态
00和状态01（取决于 “只出现一次的数字” 的各二进制位是 1 还是 0 ），而此两状态是由one来记录的（此两状态下twos恒为 0 ），因此返回ones即可。
- 遍历完所有数字后，各二进制位都处于状态
此处为语雀图册卡片，点击链接查看：https://www.yuque.com/it-coach/leetcode/xkogct#sSdmd
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# jy: ones 和 twos 分别表示 32 个状态位的对应的标签
ones, twos = 0, 0
# jy: 对每个数值 num 的 32 个二进制位同时进行操作
for num in nums:
# jy: 以下两行代码的优先顺序可互换, 优先算哪个, 则返回哪个 (如果调整为优先
# 计算 twos, 则最终返回结果也应该为 twos; 可以理解为互换状态位的含义)
ones = ones ^ num & ~twos
twos = twos ^ num & ~ones
# jy: 输入数值列表的特性会使得最终结果 twos 恒为 0
print(twos)
return ones
nums = [-2, -2, 1, 1, 4, 1, 4, 4, -4, -2]
res = Solution().singleNumber(nums)
# jy: -4
print(res)5、改写解法 1（用二进制字符串进行中间过程处理）
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
str_ = ""
for i in range(32):
sum_ = 0
for num in nums:
# jy: 右移 i 位后 (最开始 i 为 0) 并和 1 进行与运算即可获取
# num 的二进制形式的第 i 位的数值
sum_ += ((num >> i) & 1)
# jy: 将二进制位不断往左侧拼接
if sum_ % 3 == 1:
str_ = "1" + str_
else:
str_ = "0" + str_
# jy: 如果二进制结果最高位是 1, 则为负数 (对应的二进制为补码形式),
# 将 str_ 的二进制表示取反加 1 后即为该负数的绝对值 (即为该负
# 数去掉最高位的符号位后的原码表示)
if str_[0] == "1":
tmp_str = ""
for i in str_:
if i == "0":
tmp_str += "1"
else:
tmp_str += "0"
# jy: 二进制取反加 1 对应的数值等于先求得二进制对应的数值后再加 1
return - (int(tmp_str, 2) + 1)
else:
return int(str_, 2)
nums = [-2, -2, 1, 1, 4, 1, 4, 4, -4, -2]
res = Solution().singleNumber(nums)
# jy: -4
print(res)6、哈希表（不满足题意要求）
- 时间复杂度
O(n)，n 是数组的长度；空间复杂度O(n) - 哈希映射中包含最多
floor(n/3) + 1个元素，即需要的空间为O(n)
- 使用哈希映射统计数组中每个元素的出现次数，对于哈希映射中的每个键值对，键表示一个元素，值表示其出现的次数；统计完成后，遍历哈希映射即可找出只出现一次的元素
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
import collections
freq = collections.Counter(nums)
ans = [num for num, occ in freq.items() if occ == 1][0]
return ans
nums = [-2, -2, 1, 1, 4, 1, 4, 4, -4, -2]
res = Solution().singleNumber(nums)
# jy: -4
print(res)