题解 | #只出现一次的数字#

题目的主要信息：

• 一个整数数组，除了一个元素只出现了一次，其他元素都出现了两次
• 需要找出这个只出现一次的数组

方法一：哈希表

具体做法：

我们可以使用哈希表记录数组元素出现的次数，利用其快速访问特点快速去重。哈希表key值记录遇到的数组元素，第一次遇到次数计为1，后续如果再在哈希表中找到这个数字说明第二次遇到，则可以去除哈希表这个key值。

遍历结束后，如果哈希表不为空，说明找到了这个出现次数为1的数字，因为出现次数为2的都被去掉了，哈希表唯一一个元素就是。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int, int> mp;  //哈希表去重
        for(int i = 0; i < nums.size(); i++){ //遍历数组
            if(mp.find(nums[i]) != mp.end()) //遇到重复的就去除
                mp.erase(nums[i]);
            else //遇到非重复的就记录次数为1
                mp[nums[i]] = 1;
        }
        if(!mp.empty()){ //最后如果哈希表不为空，就剩下只出现一次的数字
            auto iter = mp.begin();
            return iter->first;
        }
        return 0;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历一次数组，每次哈希表操作都是$O(1)O(1)$
• 空间复杂度：$O(n)O(n)$，哈希表最大空间为不同数组元素的个数，最多有$(n-1)\mathrm{/}2+1(n-1)/2+1$个

方法二：位运算

具体做法：

性质1:0与任何整数异或运算后结果还是该整数

性质2:两个相同的数异或运算后结果为0

性质3:异或运算具有交换律

利用上述三个性质，可以遍历数组，对每个数组元素累异或运算，最后所有出现两次的整数都会被相互消掉为0，而0与出现一次的数异或还是该数字，因此最后的结果就是要求的出现次数为1次的数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0; //0异或任何数得原数
        for(int i = 0; i < nums.size(); i++) 
            res ^= nums[i]; //累异或运算消去重复元素
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，遍历一次数组
• 空间复杂度：$O(1)O(1)$，没有使用额外的辅助空间