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

题目描述

给你一个整数数组 nums，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：
输入：nums = [2,2,3,2]
输出：3

示例 2：
输入：nums = [0,1,0,1,0,1,99]
输出：99

题解

如果题面是 “除某个元素仅出现一次外，其余每个元素都出现偶数次”，那么就是一道很经典得 $O(n)$ 的异或
但是这里不是偶数次，而是三次，异或并不能处理这种状况，但是仍然可以采用类似的思路进行处理

这种题目，对于多位和一位，我们的处理逻辑是一致的
尽管异或的特性，只能处理偶数次，但是如果可以用另一个位来记录状态，那么就可以实现对 $3$ 的倍数次的处理。这样就解决了问题
假定用 ab 记录所处的状态（这里虽然严格要求 $3$ 次，但是由于不同的数字可能会在同一位是 $1$，因此应该考虑为 $3$ 的倍数次）

• 00: $3k$ 次
• 01: $3k+1$ 次
• 10: $3k+2$ 次

从中，我们只需要出现 $3k+1$ 次的情况。为了方便后续处理，这里取 01 作为 $3k+1$ 次的状态。理论上而言，状态的设定是任意的，但是如果使用 01 存储，那么在输出结果为 $3k+1$ 次的数时，可以直接输出 b（因为其他不符合的情况，b 都是 $0$）
需要特别注意的是，我们的状态中没有 11，他也不会出现在我们的数据中，因此不需要考虑

那么现在需要考虑的是，如果对这个状态进行转移

首先考虑新的数字是 $0$ 的情况，$0$ 意味着没有新数字，那么不需要改变，只需要保留原来的结果即可；接下来是新数字为 $1$，也即状态需要执行 $+1$ 擦做，00 将转换为 01，01 将转换为 10，10 将转换为 00

这里可以看作下表的形式

接下来就是实现 a 和 b 的转移了，可以使用一种很偷懒的方式进行转移：使用 “与运算” 和 “或运算” 可以实现位运算中的 if
对于 a 而言，当 c 为 $0$ 时，只有 a 为 $1$ 时输出 $1$；当 c 为 $1$ 时，只有 b 为 $1$ 时输出 $1$。也即 a = (~c & a) | (c & b)
对于 b 而言，当 c 为 $0$ 时，只有 b 为 $1$ 时输出 $1$；当 c 为 $1$ 时，只有 a 和 b 都为 $0$ 时输出 $1$。也即 b = (~c & b) | (c & (~a & ~b))

代码

func singleNumber(nums []int) int {
    a, b := 0, 0
    for _, c := range nums {
        a, b = (^c & a) | (c & b), (^c & b) | (c & ^a & ^b)
    }
    return b
}