136. 只出现一次的数字

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;}}// 如果没有找到只出现一次的数字，返回默认值0return 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 是数组长度。

如何才能做到线性时间复杂度和常数空间复杂度呢？

方法四：位运算（线性时间复杂度，常数空间复杂度）

异或运算有以下三个性质：

1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。

2. 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。

3. 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

假设数组中有 2m+1 个数，其中有 m 个数各出现两次，一个数出现一次。

令 a₁ 、a₂ 、…、a_m为出现两次的 m 个数，a_m+1为出现一次的数。

根据性质 3，数组中的全部元素的异或运算结果总是可以写成如下形式：

• (a₁⊕a₁)⊕(a₂⊕a₂)⊕⋯⊕(a_m⊕a_m)⊕a_m+1

根据性质 2 和性质 1，上式可化简和计算得到如下结果：

• 0⊕0⊕⋯⊕0⊕a_m+1=a_m+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)。