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

题目的主要信息：

给定一个整数数组，数组中有一个数出现了一次，其他数出现了两次，请找出只出现了一次的数。

方法一：

暴力法。用哈希表统计数组中数字的出现次数。首先遍历一遍数组，统计每个数字nums[i]出现的次数，如果在哈希表中已有nums[i]，则将其删除；如果哈希表中没有nums[i]，则在哈希表中设置该数字的次数为1。统计完一轮次数后，哈希表中只有只出现一次的数字，再遍历一遍哈希表，即可找到只出现一次的数字。 具体做法：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> count;//用于统计出现次数的哈希表
        for(int i=0;i<nums.size();i++){//遍历一遍数组，统计每个数字出现的次数
            if(count.find(nums[i])!=count.end()){
                count.erase(nums[i]);//如果哈希表中已有nums[i]，则删除
            }else{
                count[nums[i]]=1;//如果哈希表中没有nums[i]，则加入
            }
        }
        //最后哈希表中只有只出现一次的数字
        for(int i=0;i<nums.size();i++){//遍历一遍找到只出现一次的数字
            if(count[nums[i]]==1){
                return nums[i];
            }
        }

        return -1;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要遍历数组，数组大小为n。
• 空间复杂度：$O(n)O(n)$，哈希表的大小为$O(n)O(n)$。

方法二：

我们知道两个相同的整数异或结果为0，整数和零异或结果为整数本身。根据这个理论，我们可以用异或的方法解决这一题。遍历一遍数组，对所有数字做异或操作，如果有数字出现两次，他们将被异或成0，最后只有出现一次的数字与0异或得到它本身，异或的结果即为只出现一次的数字。

具体做法：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;//保存结果
        for (int i=0;i<nums.size();i++) {//遍历一遍数组
            res^= nums[i];//对所有元素进行异或操作
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，需要遍历数组，数组大小为n。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。