当前位置：首页 > news >正文

LeetCode 136.只出现一次的数字 | 从遍历统计到位运算极致优化

news 2026/6/16 0:39:30

📋 题目基础信息

题目序号：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(leti=0;i<nums.length;i++){constnum=nums[i];if(map[num]){// 已有记录，次数加1map[num]=map[num]+1}else{// 第一次出现，赋值为1map[num]=1}}// 第二层遍历：找出只出现一次的数字for(leti=0;i<nums.length;i++){constnum=nums[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. 🧠 解题思路

位运算是本题的标准答案、面试最优解，无需额外空间，仅需一次遍历，核心依托异或（^）运算三大核心性质：

位运算是本题的标准答案、面试最优解，依托基础遍历+异或运算特性，代码极简易懂。核心依托异或（^）运算三大核心性质：

任何数和自身异或，结果为 0：a ^ 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)	刷题提交、面试作答、最优解题