🟡 剑指 Offer 56 - II. 数组中数字出现的次数 II

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解 1_普通人的解法.py

class Solution:    def singleNumber(self, nums: List[int]) -> int:        cnt = set()        visited = set()        for num in nums:            if num in visited:                continue            if num in cnt:                cnt.remove(num)                visited.add(num)                continue            cnt.add(num)        return list(cnt)[0]

解析 2.md

数电玩家解法

某个二进制位=1时，状态机变化：

00 - 01 - 10 - 00 - ...

设二位状态为two-one，遍历的当前二进制位为n

公式

异或：

x^1 = ~x x^0 = x

与：

x&1 = xx&0 = 0

分析

低位one变化：

if two == 0:    if n == 1:        one = ~one    else:        one = oneelse:    one = 0

简化：

if two == 0:    one = one^nelse:    one = 0

再简化：

one = one ^ n & ~two

高位two变化：应该基于新的one计算

01 - 00 - 10 - 00 - ..

对调two one，发现这个状态机是不变的 所以

two = two^n & ~one

int类型的其他 31 位具有相同的运算规则，因此可将以上公式直接套用在 32 位数上。

题解 2_数电玩家的解法.py

class Solution:    def singleNumber(self, nums: List[int]) -> int:        two, one = 0, 0        for n in nums:            one = one^n & ~two            two = two^n & ~one        return one