136. 只出现一次的数字 (opens new window)

题目：

给你一个 非空 整数数组 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 是数组长度。

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

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

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

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~1~ 、a~2~ 、…、a~m~为出现两次的 m 个数，a~m+1~为出现一次的数。

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

• (a~1~⊕a~1~)⊕(a~2~⊕a~2~)⊕⋯⊕(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 是数组长度。只需要对数组遍历一次。
• 空间复杂度：O(1)。