题目基础信息题目序号LeetCode 136. 只出现一次的数字题目难度Easy简单题目地址leetcode.cn/problems/single-number题目标签数组、位运算、哈希表 题目描述给定一个非空整数数组nums除了某个元素只出现一次以外其余每个元素均出现两次。请找出那个只出现了一次的元素。✅ 题目约束必须设计并实现线性时间复杂度的算法 O(n) 解题尽量使用常数空间复杂度O(1) 实现最优解数组非空仅有唯一一个元素出现一次其余元素均成对出现 题目进阶要求不使用额外辅助空间通过位运算实现最优解法满足 O(n) 时间、O(1) 空间复杂度️ 题目示例示例1输入 nums [2,2,1]输出 1 解释仅有数字1出现一次其余数字均出现两次示例2输入 nums [4,1,2,1,2]输出 4示例3输入 nums [1]输出 1 数据范围提示数组长度1 nums.length 3 * 10^4数值范围-3 * 10^4 nums[i] 3 * 10^4 解题总览本篇收录三种完整解法由浅入深覆盖新手入门、刷题、面试核心场景JS 哈希表遍历统计逻辑直观新手零门槛快速理解题意JS 排序遍历查找常规暴力优化思路依托数组有序特性解题JS 异或位运算最优解常数空间、线性时间面试必考最优解法本篇收录两种完整解法由浅入深覆盖新手入门、刷题、面试核心场景JS 哈希表遍历统计逻辑直观新手零门槛快速理解题意JS 异或位运算最优解常数空间、线性时间面试必考最优解法 解法一哈希表遍历统计入门版1. 解题思路遍历统计是新手最容易理解的基础解法核心思想是记录频次、筛选唯一值通过额外空间换取逻辑易懂具体步骤如下创建哈希表对象/Map用于存储数组中每个数字的出现次数第一次遍历数组统计所有数字的出现频次重复数字计数叠加第二次遍历哈希表筛选出频次为 1 的数字即为答案该解法完美贴合题目题意无需算法思维纯模拟解题逻辑适合新手入门理解题目特性。2. 完整代码// 极简易懂遍历写法双层循环逻辑清晰新手友好functionsingleNumber(nums){constmap{};// 第一层遍历记录所有数字出现次数for(leti0;inums.length;i){constnumnums[i];if(map[num]){// 已有记录次数加1map[num]map[num]1}else{// 第一次出现赋值为1map[num]1}}// 第二层遍历找出只出现一次的数字for(leti0;inums.length;i){constnumnums[i];if(map[num]1){returnnum;}}return0;}3. ⏱️ 复杂度分析时间复杂度O(n)两次线性遍历数组/哈希表总复杂度为线性级别满足题目基础要求空间复杂度O(n)最坏情况下存储所有数组元素占用额外数组级内存空间4. ✅ 优缺点总结优点逻辑直白、通俗易懂无算法壁垒适合新手理解“频次统计”解题思维容错率高缺点占用额外内存空间不满足题目最优空间要求面试仅作为基础解法不推荐作为最终答案⚡ 解法二排序遍历查找常规优化版1. 解题思路排序遍历是新手容易掌握的常规解法核心思路是先排序、后比对利用本题“元素成对出现、唯一单元素”的特性查找答案具体步骤如下对原数组进行升序排序排序后成对的相同元素会相邻排列遍历有序数组每次跳过一个元素步长为2比对当前元素与下一个元素是否相等若出现当前元素与下一个元素不相等当前元素即为唯一数遍历结束未匹配则末尾元素为唯一数核心逻辑排序后数组规律为「成对、成对、唯一数」通过隔位比对可快速筛选出只出现一次的元素。2. 完整代码// 排序常规遍历循环逻辑直观无复杂语法 function singleNumber(nums) { // 数组升序排序相同元素相邻 nums.sort((a, b) a - b); // 常规步长2遍历逐个比对相邻元素 for (let i 0; i nums.length; i 2) { // 当前元素和下一个元素不相等即为唯一数 if (nums[i] ! nums[i 1]) { return nums[i]; } } return nums[nums.length - 1]; }3. ⏱️ 复杂度分析时间复杂度O(n log n)主要耗时为数组排序操作遍历仅为 O(n)整体由排序复杂度主导空间复杂度O(log n)排序算法递归调用栈占用的辅助空间属于常数级额外开销4. ✅ 优缺点总结优点思路简单直白无需哈希表额外存储逻辑贴合数组特性适合新手拓展解题思维缺点排序操作拉高时间复杂度不满足题目最优时间要求大数据量下效率低于位运算解法 解法三异或位运算遍历极简最优解1. 解题思路位运算是本题的标准答案、面试最优解无需额外空间仅需一次遍历核心依托异或^运算三大核心性质位运算是本题的标准答案、面试最优解依托基础遍历异或运算特性代码极简易懂。核心依托异或^运算三大核心性质任何数和自身异或结果为 0a ^ a 0任何数和 0 异或结果为自身a ^ 0 a异或运算满足交换律、结合律a ^ b ^ a b遍历数组所有元素逐个累计异或成对元素相互抵消为0最终剩余数值就是唯一出现的数字遍历逻辑简单、无冗余操作。核心优势单层简单遍历、无额外空间、极致高效2. 完整代码// 单层普通for遍历逻辑直白新手极易理解 const singleNumber function(nums) { let res 0; // 常规正向遍历数组逐个异或累加 for (let i 0; i nums.length; i) { res res ^ nums[i]; } return res; };3. ⏱️ 复杂度分析时间复杂度O(n)仅遍历数组一次线性时间最优复杂度空间复杂度O(1)仅使用一个常量变量存储结果无额外内存开销完全满足题目进阶要求4. ✨ 特点优势算法极致高效时间、空间均达到本题最优复杂度代码极简、执行速度快适配所有边界测试用例负数、单元素数组等面试核心考点是位运算基础经典题型必须熟练掌握 三种解法全面对比解法时间复杂度空间复杂度适用场景哈希表遍历统计O(n)O(n)新手入门、理解频次统计思维排序遍历查找O(n log n)O(log n)基础算法练习、无额外空间场景折中方案异或位运算O(n)O(1)刷题提交、面试作答、最优解题⚠️ 核心易错点核心知识点总结位运算核心牢记成对数字异或抵消、0异或任何数不变这是本题解题的核心根本所有变体题型均基于此性质哈希表坑点对象存储数字键会自动转为字符串返回结果时必须通过Number()转换避免返回字符串类型答案导致判题失败排序遍历坑点必须自定义排序函数(a,b)a-b否则数组会按字典序排序负数、多位数会出现排序错误遍历步长必须为2不可逐个比对边界场景需兼容单元素数组、负数数组位运算解法天然适配所有边界哈希表需注意类型转换排序解法需注意排序规则算法取舍哈希表以空间换易懂排序法牺牲时间换少量空间位运算是时间空间双最优解面试优先使用位运算解法