[137][中等] 只出现一次的数字 II

题目描述

137. 只出现一次的数字 II 剑指 Offer 56 - II. 数组中数字出现的次数 II

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

说明：

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

示例 1:

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

示例 2:

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

解题思路

参考: 【自动机+位运算】最详细的推导过程，没有之一

首先题目是有空间限制的, 不使用额外的空间, 否则使用哈希表就能很轻松的解决问题.

要求数字中的数字有一个上限, 这样数字对应的位长就有固定的长度. 将每个数字转换成二级制, 然后对每一位进行考虑.

逐位循环

单独的看其中某一位, 如果只出现一次的数字, 在这一位上为0, 则其他所有数字在这一位上为1的数量一定为3的倍数.

因此, 统计每一位为1的数量, 然后模3取余数, 如果余数不为0, 那么单独出现的那个数在这一位上为1, 找到所有为1的位就得到了那个数字的二级制表示.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counts = [0] * 32  # 数字位数长度限制, 最后一位表示符号
        for num in nums:
            for i in range(32):
                counts[i] += num & 1
                num >>= 1  # 这样写减少移动的次数

        res = 0
        for i in range(32):
            if counts[i] % 3 != 0:
                res += 1 << i
        return res if counts[31] % 3 == 0 else ~(res ^ 0xffffffff)  # 考虑值为负数的情况

位计算

漫画题解

上面是循环地对每一位计算1出现的次数, 但我们也可以使用位运算的便利性, 同时对所有位进行计算, 在本题目中, 这种计算相当于三进制的加法.

考虑进位, 可以将这种加法表示为如下图所示的状态机:

有向边上的数字为要加上的数值, 节点中的数字为状态. 因此可以得到如下的状态表:

state	once	twice
0	0	0
1	1	0
2	0	1

这张表的state就是图中的状态. 由于我们要用二级制机制来表示三级制的加法, 为此构造出once和twice两个辅组的二级制缓存值, 用来表示三级制中的1, 2.

现在我们考虑, 如何以once和twice代替上图, 表示状态机, 而对于二进制, 就转化成了位运算的问题.

once有两种取值, 0和1, 结果为1的状态有两种:

• input=1, once=0, twice=0

• input=0, once=1, twice=0

twice有两种取值, 0和1, 结果为1的状态有两种:

• input=1, once=1, twice=0

• input=0, once=0, twice=1

因此once和twice的状态转移方程为:

• once = (input ^ once) & (~twice)

• twice = (input ^ twice) & (once ^ twice)

代码为:

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        once, twice = 0, 0
        for num in nums:
            new_once = (num ^ once) & (~twice)
            twice = (num ^ twice) & (once ^ twice)
            once = new_once
        return once