136. 只出现一次的数字
题目：
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例：
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外，其余每个元素均出现两次。
解题：
如果不考虑时间复杂度和空间复杂度的限制方法有很多：
方法一：集合法
使用集合unordered_set存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_set<int> numSet;
for(int num : nums) {
// 如果集合中已经有当前数字，则从集合中删除
if(numSet.find(num) != numSet.end()) {
numSet.erase(num);
} else {
// 如果集合中没有当前数字，则加入集合
numSet.insert(num);
}
}
// 集合中剩下的就是只出现一次的数字
return *numSet.begin();
}
};
方法二：哈希表法
使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_map<int,int> numCount;
// 遍历数组，更新哈希表中数字的出现次数
for(int num : nums) {
numCount[num]++;
}
// 遍历哈希表，找到只出现一次的数字
for(auto& pair : numCount) {
if(pair.second == 1) {
return pair.first;
}
}
// 如果没有找到只出现一次的数字，返回默认值0
return 0;
}
};
方法三：元素之和两倍性质
由于集合保证元素无重复，所以使用集合unordered_set不重复的存储数组的元素，也就是每个元素只存储一次，重复的不存储，计算它们的和，就相当于所有数字的两倍之和。然后将原数组中的元素全部相加，就相当于只出现了一次的元素加上全部出现了两次的元素。如此看来，它们的差就是就差了一个只出现一次的元素了。
class Solution {
public:
int singleNUmber(vector<int>& nums) {
unordered_set<int> numSet;
int sumSet = 0;
int sumArray = 0;
// 遍历数组，更新集合中的元素之和和数组中的元素之和
for(int num : nums) {
if(numSet.find(num) == numSet.end()) {
numSet.insert(num);
sumSet += num;
}
sumArray += num;
}
// 计算集合中的元素之和的两倍减去数组中的元素之和，得到只出现一次的数字
return 2*sumSet - sumArray;
}
};
上述三种解法都需要额外使用 O(n) 的空间，其中 n 是数组长度。
如何才能做到线性时间复杂度和常数空间复杂度呢？
方法四：位运算（线性时间复杂度，常数空间复杂度）
异或运算有以下三个性质：
-
任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
-
任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
-
异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
假设数组中有 2m+1 个数，其中有 m 个数各出现两次，一个数出现一次。
令 a1 、a2 、…、am为出现两次的 m 个数，am+1为出现一次的数。
根据性质 3，数组中的全部元素的异或运算结果总是可以写成如下形式：
- (a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(am⊕am)⊕am+1
根据性质 2 和性质 1，上式可化简和计算得到如下结果：
- 0⊕0⊕⋯⊕0⊕am+1=am+1
因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for(auto e : nums) ret ^= e;
return ret;
}
};
复杂度分析
- 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
nt>& nums) {
int ret = 0;
for(auto e : nums) ret ^= e;
return ret;
}
};
**复杂度分析**
- 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
- 空间复杂度：O(1)。
