【每日算法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 位整数的每一位,就可以得到这个单独的数是多少了。

推广到一般情况:
如果其他数都出现了 k 次,一个数出现了一次。那么如果 k 是偶数,还是把所有的数异或起来就行了。如果 k 是奇数,那么统计每一位是 1 的个数,然后模 k 取余数就能得到那个单独的数了。

位运算

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

v2-dd7420e3ae81221fa814272301707d2f_b.jpg


初始的时候在状态 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 ,得到如下的状态自动机:

v2-72f9fc87c36649dbc6cfd67582583507_b.jpg


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

v2-96d76dc153381d6694936bad30cce6b3_b.jpg


注意观察 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:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < 32; ++i) {
            int cnt = 0;
            for (auto x : nums) {
                cnt += (x>>i)&1;
            }
            res |= (cnt%3)<<i;
        }
        return res;
    }
};

      

位运算(c++)

        class Solution {
public:
    int singleNumber(vector<int>& 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: leetcode-cn.com/problem

[2]

LeetCode 136. 只出现一次的数字: leetcode-cn.com/problem

[3]

LeetCode 面试题56 - I. 数组中数字出现的次数: leetcode-cn.com/problem

[4]

LeetCode 面试题 17.19. 消失的两个数字: leetcode-cn.com/problem

算法码上来 文章被收录于专栏

公众号「算法码上来」。godweiyang带你学习算法,不管是编程算法,还是深度学习、自然语言处理算法都一网打尽,更有各种计算机新鲜知识和你分享。别急,算法码上来。

全部评论

相关推荐

头像
10-09 19:35
门头沟学院 Java
洛必不可达:java的竞争激烈程度是其他任何岗位的10到20倍
点赞 评论 收藏
分享
11-02 09:49
已编辑
货拉拉_测试(实习员工)
热爱生活的仰泳鲈鱼求你们别卷了:没事楼主,有反转查看图片
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务