leetcode 136只出现一次的数字

LeetCode 136. 只出现一次的数字题目给定一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次找出那个只出现一次的元素。例如输入nums {4, 1, 2, 1, 2} 输出4这道题主要有两种解法哈希表unordered_map和异或运算XOR。一、方法一哈希表unordered_map1. 完整代码精简注释class Solution { public: int singleNumber(vectorint nums) { unordered_mapint,int hash; // 数字 - 出现次数 // 统计每个数字的出现次数 for(auto num : nums){ hash[num]; } // 找到出现次数为1的数字 for(auto [num,count] : hash){ if(count 1) return num; } return -1; } };2. 核心思路利用哈希表存储每个数字及其出现次数。unordered_mapint,int hash;其中Key数组中的数字。Value数字出现的次数。例如nums {4, 1, 2, 1, 2};统计后Key数字Value次数411222遍历哈希表找到count 1的数字并返回。3. 重点语法① 统计出现次数hash[num];如果num不存在哈希表会自动创建对应的键值对将整数值初始化为 0再执行加 1。② 遍历键值对for(auto [num,count] : hash)其中num键Key。count值Value。[]结构化绑定用于拆分键值对。也可以写成for(auto p : hash){ if(p.second 1){ return p.first; } }其中p.first表示 Keyp.second表示 Value。4. 复杂度分析时间复杂度平均 \(O(n)\)遍历数组统计次数再遍历哈希表。空间复杂度\(O(n)\)需要额外的哈希表。5. 方法总结哈希表解法主要分为三步创建unordered_mapint,int哈希表。遍历数组利用hash[num]统计次数。遍历哈希表返回出现次数为 1 的数字。核心利用 Key 存储数字Value 存储出现次数。二、方法二异或运算XOR1. 完整代码精简注释class Solution { public: int singleNumber(vectorint nums) { int ret 0; // 初始化异或结果 // 将所有数字依次异或 for(auto num : nums){ ret ^ num; } return ret; // 返回只出现一次的数字 } };2. 核心思路异或运算符为^。异或规则二进制位相同为 0不同为 1。aba ^ b000011101110异或具有三个重要性质① 相同数字异或为 0\[ a\oplus a0 \]② 任何数字与 0 异或等于本身\[ a\oplus 0a \]③ 异或满足交换律和结合律\[ a\oplus b\oplus a(a\oplus a)\oplus bb \]因此可以利用异或运算消除所有出现两次的数字最终只剩下出现一次的数字。3. 举例模拟nums {4, 1, 2, 1, 2};初始化int ret 0;执行过程当前数字 num异或操作ret40 ^ 4414 ^ 1525 ^ 2717 ^ 1626 ^ 24最终返回return ret; // 4从数学上理解\[ 4\oplus1\oplus2\oplus1\oplus2 \]根据交换律和结合律\[ 4\oplus(1\oplus1)\oplus(2\oplus2) \]\[ 4\oplus0\oplus0 \]\[ 4 \]所有出现两次的数字都会抵消为 0最终就是 0 与只出现一次的数字异或结果为该数字本身。4. 重点语法ret ^ num;等价于ret ret ^ num;其中^按位异或运算。^异或赋值运算。注意^不是乘方运算。5. 复杂度分析时间复杂度\(O(n)\)只遍历数组一次。空间复杂度\(O(1)\)只使用一个额外变量ret。6. 方法总结异或解法主要分为三步初始化ret 0。遍历数组将每个数字与ret异或。所有成对出现的数字相互抵消最终返回ret。核心相同数字异或为 00 与任何数字异或等于数字本身。三、两种方法对比对比哈希表异或核心思想统计出现次数相同数字相互抵消数据结构unordered_map不需要时间复杂度平均 \(O(n)\)\(O(n)\)空间复杂度\(O(n)\)\(O(1)\)优点容易理解适用范围广代码简洁空间效率高缺点需要额外空间依赖题目中特定的出现次数条件四、最终记忆模板哈希表统计次数找到出现一次的数字。unordered_mapint,int hash; for(auto num : nums){ hash[num]; } for(auto [num,count] : hash){ if(count 1) return num; }异或相同数字抵消剩下唯一数字。int ret 0; for(auto num : nums){ ret ^ num; } return ret;最后总结哈希表和异或都能解决这道题但题目要求线性时间复杂度和常数额外空间复杂度因此异或才是本题最优解法。以后遇到类似题目可以这样判断需要统计数字出现次数优先考虑unordered_map。需要判断数字是否出现过优先考虑unordered_set。所有数字出现两次只有一个数字出现一次优先考虑异或运算。