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。所有数字出现两次只有一个数字出现一次优先考虑异或运算。

leetcode 136只出现一次的数字

相关推荐

YOLOv5s部署RK3588 NPU实战：INT8量化与性能调优避坑指南

SpringBoot+Vue构建高效航班进出港管理系统

智能安防转型实战：从卖设备到卖方案，AI算法与边缘计算落地指南

更多资讯

铝代木构件筑文旅地标承古韵兼济长效品质

PHP防伪证书系统：TCPDF动态生成PDF与防伪验证闭环

ISO/SAE 21434落地指南：从TARA分析到CAL等级的工程实践

轻量PHP在线排版工具：解决粘贴乱码与段落失序问题

沁言学术、Jenni AI等5款AI科研工具盘点，论文写作各环节谁补位

EPICS电机驱动开发：四层架构与ASYN实时通信深度解析

今日更新

小波包能量谱原理与MATLAB实现：从频带分解到故障特征提取

基于LSTM的网易云音乐评论情感分析：数据清洗与模型调优实战

Alpha-Beta剪枝与极大极小值算法：博弈树搜索原理与实战优化

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？