PROBLEM

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

难度 中等

MY ANSWER

哈希表存储出现次数，时间空间复杂度为O(n)。

BETTER SOLUTION

基本思想：
Picture1.png

可以使用基础做法来实现，数组统计二进制位的1的个数。时间复杂度O(n)，空间复杂度O(1)。自动机做法复杂度相同，但计算次数更少。

有限状态自动机

Picture3.png

根据状态转移图得出布尔运算式：

Picture4.png

Picture5.png

以上是对数字的二进制中 “一位” 的分析，而 int 类型的其他 31 位具有相同的运算规则，因此可将以上公式直接套用在 32 位数上。

遍历完所有数字后，各二进制位都处于状态 00 和状态 01 （取决于 “只出现一次的数字” 的各二进制位是 1 还是 0 ），而此两状态是由 one 来记录的（此两状态下 two 恒为 0 ），因此返回 one 即可。

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
    	int ones = 0, twos = 0;
        for(int num : nums){
            ones = ones ^ num & ~twos;
            twos = twos ^ num & ~ones;
        }
        return ones;
    }   
};

SUMMARY

  • 此类问题，要思考二进制位的特性，使用自动机、位运算来解决。

  • 状态转移图化简：

    真值表：

n two one one’
0 0 0 0
0 0 1 1
0 1 0 0
1 0 0 1
1 0 1 0
1 1 0 0

nab + nab = b

a(nb + n ~b) = ~an^b = b

即one = one ^ n & ~two