【每日算法Day 72】谷歌面试题：又双叒叕是位运算，最详细的自动机推导过程...

【每日算法Day 72】谷歌面试题：又双叒叕是位运算，最详细的自动机推导过程...

题目链接

LeetCode 137. 只出现一次的数字 II[1]

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例1

输入：[2,2,3,2]输出：3

示例2

输入：[0,1,0,1,0,1,99]输出：99

题解

逐位考虑

我们单独看二进制某一位，先不看单独的那个数，其他所有数字都出现了 3 次，所以那一位是 1 的个数一定是 3 的倍数。

再考虑这个出现一次的数，如果这一位是 1 ，那么这一位 1 的次数模 3 为 1 ，否则的话模 3 就是 0 。

那么就很简单了，统计一下有多少个数这一位上是 1 ，然后模 3 取余数，结果就是这个单独的数这一位上的值了。

遍历 32 位整数的每一位，就可以得到这个单独的数是多少了。

推广到一般情况：如果其他数都出现了 次，一个数出现了一次。那么如果 是偶数，还是把所有的数异或起来就行了。如果 是奇数，那么统计每一位是 1 的个数，然后模

位运算

我们还可以用自动机来做这题，根据某一位 1 的个数，我们可以得到如下的状态自动机：

初始的时候在状态 0 （有 0 个 1），然后如果下一个数这一位是 1，就进入状态 1（有 1 个 1），接着如果下一个数这一位是 1，就进入状态 2（有 2 个 1），接着如果下一个数这一位是 1，就进入状态 3（有 3 个 1），最后如果再来了一个数这一位还是 1，就说明是一个新的数了，等价于回到了状态 1。而每个状态如果来的数这一位是 0 ，都会保持状态不变。

当然这个自动机还可以简化，注意观察可以发现状态 3 和状态 0 是等价的（输入 0 都保持不变，输入 1 都会进入状态 1）。所以我们将状态 1 和状态 3 合并为一个状态 0 ，得到如下的状态自动机：

因为一共有三个状态，所以我们需要用两个变量来表示状态。用 ​​once​​​ 表示是否在状态 1，用 ​​twice​​ 来表示是否在状态 2 。那么两个变量都为 0 就表示在状态 0 。然后可以得到如下的状态转移表：

注意观察 ​​once​​​ 只有两种情况下转移后为 1 。一种是 ​​once=0, twice=0, x=1​​​ ，另一种是 ​​once=1, twice=0, x=0​​​ 。其他所有情况下 ​​once​​​ 都转移为 0 。这两种情况都满足 ​​x^once=1​​​ 并且 ​​twice=0​​​ ，所以 ​​once​​​ 的转移就是 ​​once = (x^once) & (~twice)​​ 。

同理，观察 ​​twice​​​ 只有两种情况下转移后为 1 。一种是 ​​once=1, twice=0, x=1​​​ ，另一种是 ​​once=0, twice=1, x=0​​​ 。其他所有情况下 ​​twice​​​ 都转移为 0 。这两种情况都满足 ​​x^twice=1​​​ 并且 ​​once^twice=1​​​ ，所以 ​​twice​​​ 的转移就是 ​​twice = (x^twice) & (once^twice)​​ 。但是！！！​​once​​​ 已经抢先一步转移过了，所以值已经变掉了，一个解决方法就是用临时变量保存一下前一个状态的 ​​once​​​ 值。另一个方法就是，这两种情况下，​​once​​​ 都会转移到 0 ，所以判断条件直接用转移后的 ​​once=0​​​ 就行了，随后转移就是 ​​twice = (x^twice) & (~once)​​ 。

代码

逐位考虑（c++）（代码有误，正确代码见留言第一条）

class Solution {public: vector missingTwo(vector& nums) { int n = nums.size(); int x = 0; for (auto i : nums) x ^= i; for (int i = 1; i <= n+2; ++i) x ^= i; int lb = x & -x; int y = 0; for (auto i : nums) { if (i&lb) y ^= i; } for (int i = 1; i <= n+2; ++i) { if (i&lb) y ^= i; } return {y, y^x}; }};

位运算（c++）

class Solution {public: int singleNumber(vector& nums) { int once = 0, twice = 0; for (auto x : nums) { once = (once^x)&(~twice); twice = (twice^x)&(~once); } return once; }};

相关题目

LeetCode 136. 只出现一次的数字[2]

LeetCode 面试题56 - I. 数组中数字出现的次数[3]

LeetCode 面试题 17.19. 消失的两个数字[4]

参考资料

[1]

LeetCode 137. 只出现一次的数字 II: ​​136. 只出现一次的数字: ​​面试题56 - I. 数组中数字出现的次数: ​​面试题 17.19. 消失的两个数字: ​​https://leetcode-cn.com/problems/missing-two-lcci/​​

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。