LC136 Single Number

本题链接：Single Number

本题标签：Hash Table，Bit Manipulation

本题难度：

英文题目 中文题目

---

本题是137.Single Number II的简化版。

方案1： 利用map统计数字出现次数，然后遍历map找到出现次数为1的数字即为答案。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        unordered_map<int, int> mp;
        for(auto n : nums)
            ++mp[n];
        
        for(auto ele : mp)
            if(ele.second == 1)
            {
                res = ele.first;
                break;
            }
        return res;
    }
};

时间复杂度：

空间复杂度：

---

方案2： 利用数电知识推导出位运算公式

根据题意我们可以得出如下逻辑运算：

1. 当某一个数出现2次时，其结果应为0，即。
2. 当某一个数出现1次时，其结果应为1，即。

这里*代表某种运算逻辑，不是乘法的含义。
那么我们可以推理出如下结论：

1. 某一个数出现0次为0，出现1次为1，出现2次为0。说明这是一种循环状态，其中有效状态为前2个，可以用模2运算来表达为0、1这2种状态。
2. 用二进制来记录这2种状态需要至少1位二进制位，即可以用0、1来代表。
3. 这样输入数字的每一个二进制位都可以用这种方式表达，因为二进制位的运算是互相独立的。如果再输入一个数字，对于每一位的位运算操作就可以表达如下：
   • 如果输入的是0，0->0，1->1，即2种状态无变化。
   • 如果输入的是1，0->1，1->0。

接下来我们就可以求出逻辑表达式了：

设当前状态为 ，输入为 ，则 的真值表如下：

#
1	0	0	0
2	1	0	1
3	0	1	1
4	1	1	0

这里我们取 的所有行中的 组成逻辑表达式，因为这代表了1这种情况，即数字出现1次的情况：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < nums.size(); ++i)
            res = res ^ nums[i];
        
        return res;
    }
};

时间复杂度：

空间复杂度：