专栏首页机器视觉CV【位运算】只出现一次的数字 II,数电的知识终于用上了!

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

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

问题

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

本文分享自微信公众号 - 机器视觉CV(AIandCV),作者:TankCode

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【C++简明教程】Python和C++指定元素排序比较

    在 Python 中,常用的排序就是 sorted ,对于列表这种数据结构来说,还有 sort 方法

    机器视觉CV
  • 【C++简明教程】找数组或者Vector中最大最小值的索引

    在 Python 中,我们可以使用 numpy 库快速实现,那接下来就看看 C++ 是怎么实现的吧

    机器视觉CV
  • 【C++简明教程】随机数生成

    【C++ 简明教程】每次更新将会以代码块的形式发布,可以作为手册或者模块以供查询。

    机器视觉CV
  • LeetCode 209. Minimum Size Subarray Sum(DP)

    题解:可以用动态规划,我就是用动态规划过的,但是确实不是最简单的解法,看了题解最简单的是双指针,

    ShenduCC
  • 扑克牌中的顺子

    从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数...

    木子星兮
  • Leetcode 53 Maximum Subarray

    Find the contiguous subarray within an array (containing at least one number) w...

    triplebee
  • 内功修炼-算法1

    给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

    Share猿
  • 每日算法系列【LeetCode 287】寻找重复数

    给定一个包含 个整数的数组 ,其数字都在 到 之间(包括 和 ),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。

    godweiyang
  • Leetcode 26 Remove Duplicates from Sorted Array

    Given a sorted array, remove the duplicates in place such that each element app...

    triplebee
  • LeetCode每日一题53: 最大子序和

    给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

    benny

扫码关注云+社区

领取腾讯云代金券