题目

题解

1. 有限状态机

详细题解看这里。这里放几张来自该题解的图。详细题解还是看 Krahets 大神的题解吧。




  • 时间复杂度: $O(n)$
  • 空间复杂度: $O(1)$
    重点掌握one和two的状态转换方程：
    one = (one ^ n) & ~two;
    two = (two ^ n) & ~one;
class Solution {//三个方法。1. 有限状态机
public:
    int singleNumber(vector<int>& nums) {
        int two = 0, one = 0;
        for(auto n : nums){
            one = (one ^ n) & ~two;
            two = (two ^ n) & ~one;
        }
        return one;
    }
};

2. 挨个统计每一位的次数

这道题有一个性质是，统计每一位的个数，然后对3取余，剩下的就是要求的数。有限状态机的方法也是用的这个性质。但是挨个统计每一位会比较慢。题目限定num了最多为32位，因此要挨个相加32位

  • 时间复杂度: $O(32n)$
  • 空间复杂度: $O(1)$
class Solution {//三个方法。2. 挨个统计每一位
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;//定义res存结果
        //挨个统计每一位1的个数，最多32位
        for(int i = 0; i < 32; ++i){
            int count = 0;
            //统计每一个数
            for(auto n : nums){
                //与（1<<i）与，大于0说明该位为1，等于0说明该位为0
                if((n & (1 << i)) > 0) count++;
            }
            //将计数值对3取余，为1的话结果这一位置1
            if(count % 3 == 1) res ^= (1 << i);
        }
        return res;
    }
};

3. 哈希存值法

这个方法比较好理解，就是挨个计数存入unordered_map，然后取value为1的key。遍历两遍

  • 时间复杂度: $O(n)$
  • 空间复杂度: $O(1)$
class Solution {//三个方法。3. 哈希存值
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> m;
        for(auto n : nums) m[n]++;//统计每个数组的个数
        //为1就返回该key
        for(auto m_pair : m){
            if(m_pair.second == 1) return m_pair.first;
        }
        return -1;

    }
};