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(log⁡N)O(\log N)O(logN)而std::unordered_map底层是哈希表时间复杂度是真正的O(1)O(1)O(1)。为了严格满足题目的线性时间要求我们应当使用unordered_map。 C 代码实现 (哈希表法)classSolution{public:intsingleNumber(vectorintnums){// 使用 unordered_map 保证 O(1) 的插入和查找时间unordered_mapint,intmp;// 第一次遍历统计每个数字出现的频率for(inti0;inums.size();i){mp[nums[i]];}// 第二次遍历在哈希表中寻找频率为 1 的数字for(autott:mp){if(tt.second1)returntt.first;}return-1;// 理论上不会走到这里}}; 解法二异或运算 (XOR) 的降维打击题目给出了极其严苛的条件时间O(N)O(N)O(N)且空间O(1)O(1)O(1)。这意味着我们不能借助任何数组、哈希表等外部数据结构。这道题是计算机科学中利用**“位运算”的绝对经典。我们需要用到异或运算 (^)**。异或运算有三个极其优美的数学性质任何数和 0 做异或运算结果仍然是原来的数a⊕0aa \oplus 0 aa⊕0a任何数和其自身做异或运算结果是 0a⊕a0a \oplus a 0a⊕a0异或运算满足交换律和结合律a⊕b⊕a(a⊕a)⊕b0⊕bba \oplus b \oplus a (a \oplus a) \oplus b 0 \oplus b ba⊕b⊕a(a⊕a)⊕b0⊕bb破局点题目中明确指出“除了某个元素只出现一次以外其余每个元素均出现两次”。只要我们将数组中的所有元素全部进行异或运算根据交换律和结合律那些成对出现的数字就会自动排在一起互相抵消成0。最终剩下的就是那个孤零零的、只出现了一次的数字 C 代码实现 (极简异或法)classSolution{public:intsingleNumber(vectorintnums){// 初始值为 0因为 0 异或任何数等于任何数本身intres0;// 遍历数组将所有数字进行异或累加for(autoe:nums){res^e;}// 成对的数字全变成 0 抵消了最后留下来的 res 就是只出现一次的数字returnres;}};