原题链接:
https://leetcode.cn/problems/single-number-ii/description

要求线性时间复杂度 常数级空间

解法1: 哈希

可以通过但不符合常数级空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // 数字 -> 出现次数
        unordered_map<int,int>hash;
        for(auto & e : nums){
            hash[e]++;
        }

        for(auto it = hash.begin() ; it != hash.end() ; it++){
            if(it->second == 1){
                return it->first;
            }
        }
        return 0;
    }
};

解法2: 位数统计(位运算)

位数统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
    位数统计 
    使用一个长度为32 的数组cnt[] 记录下所有数值的每一位共出现了多少次1
    再对cnt[] 数组的每一位进行mod 3操作 重新拼凑出只出现一次的的数值
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int>cnt(32,0);
        for(auto & x : nums){
            for(int i = 31 ; i >= 0 ; i--){
                cnt[i] += (x >> i) & 1;
            }
        }

        int ans = 0;

        for(int i = 0 ; i < 32 ; i++){
            ans += (cnt[i] % 3) << i;
        }

        return ans;
    }
};

解法3: 有限状态自动机

这个题状态表示后 还要结合数电的知识对状态转移化简 个人认为不是一个好的方法 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
    有限状态自动机:
    对于所有数字中的某二进制位1的个数 存在3种状态 即对3余数位0,1,2
    用00 表示余数为0的状态 01表示余数为1的状 10表示余数为2的状态
    通过卡诺图化简可得状态转移图
*/
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;
    }
};