这是一道位运算的题目,感觉解法比较新奇,分享一下~
https://leetcode-cn.com/problems/single-number-ii/
LeetCode137: 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗? 示例 1: 输入: [2,2,3,2] 输出: 3 示例 2: 输入: [0,1,0,1,0,1,99] 输出: 99
数组中除某个元素外,其他的会出现 3 次,举个例子,给定数组:nums=[a, a, a, b, c, c, c],那么有等式 3 (a+b+c)=sum (nums)+2b,那么我们要的结果就是 b=(3 (a+b+c)-sum (nums))/2
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return (3*sum(set(nums))-sum(nums))//2
该思路源于作者:TankCode
来源:https://leetcode-cn.com/problems/single-number-ii/solution/luo-ji-dian-lu-jiao-du-xiang-xi-fen-xi-gai-ti-si-l/
这道题的引申义就是要让我们找到一种运算方式,使得 a×a×a=0 且 0×a=a×0=a, ×
代表运算方式。
若读者学过数电的话,应该就会反映过来,这不就是类似于真值表找通式的过程吗?
设当前状态为 XY,输入为 Z,那么我们可以分别为 X 和 Y 列出真值表
的行的 X,Y,Z 的最小项,然后 OR 起来)
化简完就是
替换原来 Y 的值形成新的逻辑表,这个逻辑表对 X 来说是跟求 Y 的时候的逻辑表是同构的。也就是说先更新 Y 以后,拿
去更新 X 时是可以直接套用刚才求的表达式的,也就是
class Solution:
def singleNumber(self, nums: List[int]) -> int:
X,Y=0,0
for Z in nums:
Y=Y^Z & ~X
X=X^Z & ~Y
return Y
而这个写法是上述介绍的直接用了
去计算
,可能有人这里不太明白,其实我们也可以 naive 地推出用旧 Y 去计算
的表达式
class Solution:
def singleNumber(self, nums: List[int]) -> int:
X,Y=0,0
for Z in nums:
Y_new=Y^Z & ~X
X=(X&~Y&~Z)|(~X&Y&Z)
Y=Y_new
return Y
或者下面这个程序,原因是
class Solution:
def singleNumber(self, nums: List[int]) -> int:
X = 0
Y = 0
for Z in nums:
Y_new = ~X&(Y&~Z | ~Y&Z)
X = (X&~Y&~Z | ~X&Y&Z)
Y = Y_new
return Y