首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【位运算】只出现一次的数字 II,数电的知识终于用上了!

【位运算】只出现一次的数字 II,数电的知识终于用上了!

作者头像
机器视觉CV
发布2020-07-23 11:13:09
6330
发布2020-07-23 11:13:09
举报
文章被收录于专栏:机器视觉CV机器视觉CV

这是一道位运算的题目,感觉解法比较新奇,分享一下~

问题

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, × 代表运算方式。

若读者学过数电的话,应该就会反映过来,这不就是类似于真值表找通式的过程吗?

  1. 思路分析
  • 第一时间应该想到的是找到一种逻辑操作,可以满足 1×1×1=0 且 0×1=1×0=1 ,其中 × 为这种新逻辑操作符。根据这个,我们可以想到
  • 出现 0 次为 0,出现 1 次为 1,出现 2 次的值无所谓,出现 3 次就又回到 0,也就是说,我们一共需要记录 3 种状态:0 次,1 次,2 次,之后次数都是这三种状态的循环。其实这也就是一个模三运算。
  • 记录两个状态需要的是一位二进制 0/1,那么记录三种状态需要的是至少两位二进制,可以是 00, 01, 10, 11,这里我们只需要选其中任意三个状态即可,例如:00,01,10,分别代表 0 次 1 次 2 次。
  • 用 00 代表 0 次,01 代表出现 1 次是因为刚好对应数字原本那位上 0 代表 0 次,1 代表 1 次,这样可以方便写程序,不这么选也可以,但最后你自己要有个映射规则。至于 2 次的编码无所谓,10 和 11 都可以,反正最后答案也不要它,只是个中间状态,辅助我们计算的。
  • 那么对于输入数字的每一位二进制位,都可以用这三种状态表示。如果再输入一个数字,对于每一位上,我们的操作可以化为:
    • 新输入的是 0(即 00),三种状态都维持不变,00→00,01→01,10→10
    • 新输入的是 1(即 01),00→01,01→10,10→00
  1. 求逻辑表达式

设当前状态为 XY,输入为 Z,那么我们可以分别为 X 和 Y 列出真值表

  • 对于 Y,转化为逻辑表达式就是(取所有
Y_{new}=1

的行的 X,Y,Z 的最小项,然后 OR 起来)

Y_{new}=\overline{XY}Z+\overline{X}Y\overline{Z}

化简完就是

Y_{new}=\overline{X}(Y\oplus Z)
  • 同理也可以得出 X 的逻辑表达式,但是这里有一个 tricky 的地方,不用再去求新的表达式。我们先更新完 Y,然后把 放到逻辑表中
Y_{new}

替换原来 Y 的值形成新的逻辑表,这个逻辑表对 X 来说是跟求 Y 的时候的逻辑表是同构的。也就是说先更新 Y 以后,拿

Y_{new}

去更新 X 时是可以直接套用刚才求的表达式的,也就是

X_{new}=\overline{Y}(X\oplus Z)
  • 这样就算做完了,把所有数以依次输入,然后不断更新这两个状态,最终,出现 3 次的位都成 0(也就是 00),出现 1 次的位都成了 1(也就是 01)。我们最后直接返回状态 Y 就是要的答案。(另外辅助验证,最后 X 应该为全 0,因为最后所有位的状态要么是 00,即出现 3 次的数的位,要么是 01,即出现 1 次的数的位)
代码
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

而这个写法是上述介绍的直接用了

Y_{new}

去计算

X_{new}

,可能有人这里不太明白,其实我们也可以 naive 地推出用旧 Y 去计算

X_{new}

的表达式

X{new}=X\overline{YZ}+\overline{X}YZ
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

或者下面这个程序,原因是

Y\overline{Z}+\overline{Y}Z=Y^{\wedge} Z
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
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-06-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 机器视觉CV 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题
  • 思路
    • 数值解法
      • 逻辑电路
        • 代码
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档