LeetCode 热题 100_只出现一次的数字（96_136_简单_C++）（哈希表；哈希集合；排序+遍历；位运算）

题目描述：

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

输入输出样例：

示例 1：
输入：nums = [2,2,1]
输出：1

示例 2：
输入：nums = [4,1,2,1,2]
输出：4

示例 3：
输入：nums = [1]
输出：1

提示：
1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
除了某个元素只出现一次以外，其余每个元素均出现两次。

题解：

解题思路：

思路一（哈希表）：

1、使用一个哈希表来存储每个数值出现的次数（key代表数值，value代表数值对应出现的次数）。遍历一遍数组来记录每个数值出现的次数，再遍历一遍哈希表找出出现次数为1的数值。
2、复杂度分析：
① 时间复杂度：O(n)，n为数组中元素的个数，遍历一遍数组，遍历一遍哈希表。
② 空间复杂度：O(n)，n为数组中元素的个数，使用哈希表存储不同的元素。

思路二（哈希集合）：

1、使用一个哈希集合来存储一个元素，若集合之前没有存储相同元素则插入集合中，若集合之前存在相同元素则将集合中值相同的元素删除。遍历完数组最后剩下的元素为只出现一次的数字。

2、复杂度分析
① 时间复杂度：O(n)，n为数组中元素的个数，遍历一遍数组。
② 空间复杂度：O(n)，n为数组中元素的个数，使用哈希集合储不同的元素（最坏的情况，前半部分元素不同）。

思路三（排序+遍历）：

1、排序使得相同元素凑到一起。每次比较排序后相邻的两个元素，若不同则返回相邻元素中的前一个。

2、复杂度分析
① 时间复杂度：O(nlogⁿ)，n为数组中元素的个数，快速排序后遍历一遍数组。
② 空间复杂度：O(nlogⁿ)，n为数组中元素的个数，快速所占用的存储空间。

思路四（位运算）：

1、我们可以通过元素之间的位运算来求只出现一次的数字。
0⊕1=1 1⊕0=1 0⊕0=0 1⊕1=0
a⊕0 =a a⊕a=0 a⊕b⊕a = a⊕a⊕b =b

2、复杂度分析
① 时间复杂度：O(n)，n为数组中元素的个数，遍历一遍数组。
② 空间复杂度：O(1)。

代码实现

代码实现（思路一（哈希表））：

class Solution1 {
public:// 定义一个函数，返回数组中只出现一次的数字int singleNumber(vector<int>& nums) {// 创建一个 unordered_map 来统计每个数字出现的次数unordered_map<int, int> mp;// 遍历数组中的每个数字for (const int &i : nums) {mp[i]++;  // 对每个数字出现的次数进行自增}// 遍历 unordered_map，查找出现次数为 1 的数字for (auto &k : mp) {if (k.second == 1) {  // 如果某个数字的出现次数是 1return k.first;    // 返回该数字}}// 如果没有找到单一出现的数字，返回 0return 0;}
};

代码实现（思路二（哈希集合））：

class Solution2 {
public:// 定义一个函数，返回数组中只出现一次的数字int singleNumber(vector<int>& nums) {// 创建一个 unordered_set 来存储数字unordered_set<int> mp_set;// 遍历数组中的每个数字for (int i = 0; i < nums.size(); i++) {// 如果数字已经存在于 set 中，则将其移除if (mp_set.count(nums[i])) {mp_set.erase(nums[i]);  // 移除出现过的数字} else {// 如果数字不存在于 set 中，则添加它mp_set.insert(nums[i]);  // 将数字添加到 set 中}}// set 中最后剩下的唯一元素就是只出现一次的数字，返回该数字return *mp_set.begin();  // 返回 set 中的第一个元素}
};

代码实现（思路三（排序+遍历））：

class Solution3 {
public:// 定义一个函数，返回数组中只出现一次的数字int singleNumber(vector<int>& nums) {// 首先对数组进行排序sort(nums.begin(), nums.end());// 遍历排序后的数组，从索引 1 开始，步长为 2for (int i = 1; i < nums.size(); i += 2) {// 如果当前元素与前一个元素不相等，说明前一个元素是只出现一次的元素if (nums[i] != nums[i - 1]) {return nums[i - 1];  // 返回前一个元素}}// 如果没有在循环中找到只出现一次的元素，返回最后一个元素return nums[nums.size() - 1];  // 返回数组中的最后一个元素}
};

代码实现（思路四（位运算））：

class Solution4 {
public:// 定义一个函数，返回数组中只出现一次的数字int singleNumber(vector<int>& nums) {int ans = 0;  // 初始化变量 ans 为 0// 遍历输入数组中的每一个元素for (const auto &i : nums) {// 使用按位异或运算来处理数组中的元素ans ^= i;  // 每次将 ans 与当前元素进行异或运算}// 返回最终结果return ans;  // ans 存储的是只出现一次的数字}
};

以思路四为例进行调试

#include<iostream>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<algorithm>
using namespace std;/**方法四（位运算）* 0⊕1=1   1⊕0=1   0⊕0=0   1⊕1=0* a⊕0 =a   a⊕a=0   a⊕b⊕a = a⊕a⊕b =b*/
class Solution4 {
public:// 定义一个函数，返回数组中只出现一次的数字int singleNumber(vector<int>& nums) {int ans = 0;  // 初始化变量 ans 为 0// 遍历输入数组中的每一个元素for (const auto &i : nums) {// 使用按位异或运算来处理数组中的元素ans ^= i;  // 每次将 ans 与当前元素进行异或运算}// 返回最终结果return ans;  // ans 存储的是只出现一次的数字}
};int main(int argc, char const *argv[])
{vector<int> nums={4,1,2,1,2};Solution4 s;cout<<s.singleNumber(nums);return 0;
}

LeetCode 热题 100_只出现一次的数字（96_136)原题链接
欢迎大家和我沟通交流(✿◠‿◠)