【Hot 100 刷题计划】 LeetCode 136. 只出现一次的数字 | C++ 哈希表异或基础解法
LeetCode 136. 只出现一次的数字
📌 题目描述
题目级别：简单
给你一个非空整数数组nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例 1:
输入：nums = [2,2,1]
输出：1示例 2:
输入：nums = [4,1,2,1,2]
输出：4
💡 解法一：哈希表计数法
面对“统计元素出现次数”的问题，人类的第一直觉通常是使用哈希表（Hash Map）或者字典。
我们只需要遍历一次数组，把每个数字作为 Key，出现的次数作为 Value 存起来。最后再遍历一次哈希表，找到那个 Value 为 1 的 Key，就是我们要找的落单数字。
⚠️ 细节提醒：
在 C++ 中，std::map底层是红黑树，查找和插入的时间复杂度是O(logN)O(\log N)O(logN)；而std::unordered_map底层是哈希表，时间复杂度是真正的O(1)O(1)O(1)。为了严格满足题目的线性时间要求，我们应当使用unordered_map。
💻 C++ 代码实现 (哈希表法)
classSolution{public:intsingleNumber(vector<int>&nums){// 使用 unordered_map 保证 O(1) 的插入和查找时间unordered_map<int,int>mp;// 第一次遍历：统计每个数字出现的频率for(inti=0;i<nums.size();i++){mp[nums[i]]++;}// 第二次遍历：在哈希表中寻找频率为 1 的数字for(autott:mp){if(tt.second==1)returntt.first;}return-1;// 理论上不会走到这里}};💡 解法二：异或运算 (XOR) 的降维打击
题目给出了极其严苛的条件：时间O(N)O(N)O(N)且空间O(1)O(1)O(1)。这意味着我们不能借助任何数组、哈希表等外部数据结构。
这道题是计算机科学中利用**“位运算”的绝对经典。我们需要用到异或运算 (^)**。
异或运算有三个极其优美的数学性质：
- 任何数和 0 做异或运算，结果仍然是原来的数：a⊕0=aa \oplus 0 = aa⊕0=a
- 任何数和其自身做异或运算，结果是 0：a⊕a=0a \oplus a = 0a⊕a=0
- 异或运算满足交换律和结合律：a⊕b⊕a=(a⊕a)⊕b=0⊕b=ba \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = ba⊕b⊕a=(a⊕a)⊕b=0⊕b=b
破局点：
题目中明确指出“除了某个元素只出现一次以外，其余每个元素均出现两次”。
只要我们将数组中的所有元素全部进行异或运算，根据交换律和结合律，那些成对出现的数字就会自动排在一起互相抵消成0。最终剩下的，就是那个孤零零的、只出现了一次的数字！
💻 C++ 代码实现 (极简异或法)
classSolution{public:intsingleNumber(vector<int>&nums){// 初始值为 0，因为 0 异或任何数等于任何数本身intres=0;// 遍历数组，将所有数字进行异或累加for(autoe:nums){res^=e;}// 成对的数字全变成 0 抵消了，最后留下来的 res 就是只出现一次的数字returnres;}};