东方市网站建设_网站建设公司_Angular_seo优化

对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 136. 只出现一次的数字

1. 题目描述

1.1 问题陈述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

要求:

• 算法应具有线性时间复杂度 O(n)。
• 尽量不使用额外空间，即实现常数空间复杂度 O(1)。

2. 问题分析

2.1 输入输出分析

输入为一个整数数组nums，输出为该数组中唯一一个只出现一次的整数。数组保证非空，且除一个元素外，所有元素都恰好出现两次。

2.2 约束条件分析

• 数组长度 n 满足 1 ≤ n ≤ 3 * 10^4，但算法需适应任意规模。
• 元素为整数，范围可能包括负数和大数，但JavaScript中数字类型可安全处理。
• 核心挑战：在 O(n) 时间和 O(1) 空间内解决，排除暴力搜索或排序等低效方法。

3. 解题思路

3.1 思路一：使用哈希表

遍历数组，用哈希表记录每个数字的出现次数，再查找次数为1的数字。时间复杂度 O(n)，空间复杂度 O(n)。

3.2 思路二：使用集合和数学

利用 Set 去重，计算集合元素和的两倍与数组总和的差。由于其他元素出现两次，差值即为目标。时间复杂度 O(n)，空间复杂度 O(n)。

3.3 思路三：使用异或运算（最优解）

利用异或位运算的性质：

• a ^ a = 0（相同数字异或归零）
• a ^ 0 = a（任何数与0异或不变）
• 异或满足交换律和结合律
  遍历数组，对所有元素进行异或，成对数字抵消，最终结果即为只出现一次的数字。时间复杂度 O(n)，空间复杂度 O(1)，是最优解。

4. 各思路代码实现

4.1 思路一代码实现（哈希表）

/** * 使用哈希表统计频率 * 步骤： * 1. 创建哈希表（Map）记录每个数字的出现次数。 * 2. 遍历数组，更新哈希表计数。 * 3. 遍历哈希表，返回计数为1的数字。 * 时间复杂度：O(n)，遍历数组和哈希表各一次。 * 空间复杂度：O(n)，哈希表存储最多 n/2 + 1 个键值对。 */varsingleNumber=function(nums){// 创建哈希表，使用 Map 以支持任意整数键constfreqMap=newMap();// 第一次遍历：统计每个数字的出现次数for(letnumofnums){// 如果 num 已存在，计数加1；否则初始化为1freqMap.set(num,(freqMap.get(num)||0)+1);}// 第二次遍历：查找出现一次的数字for(let[num,count]offreqMap){if(count===1){returnnum;// 找到目标}}// 根据题目保证，此处不会执行，但为代码完整性返回-1return-1;};

4.2 思路二代码实现（集合和数学）

/** * 使用集合和数学公式 * 步骤： * 1. 使用 Set 去重，得到所有不重复数字。 * 2. 计算 Set 中所有数字的和（setSum）。 * 3. 计算数组所有数字的和（arraySum）。 * 4. 应用公式：目标 = 2 * setSum - arraySum。 * 时间复杂度：O(n)，遍历数组和集合各一次。 * 空间复杂度：O(n)，Set 存储最多 n/2 + 1 个元素。 */varsingleNumber=function(nums){// 创建 Set 去重constnumSet=newSet(nums);// 计算 Set 中数字的和letsetSum=0;for(letnumofnumSet){setSum+=num;}// 计算数组所有数字的和letarraySum=0;for(letnumofnums){arraySum+=num;}// 公式推导：设目标为 x，其他数字各出现两次，则 setSum = x + 其他数字和，arraySum = x + 2 * 其他数字和// 因此，x = 2 * setSum - arraySumreturn2*setSum-arraySum;};

4.3 思路三代码实现（异或运算）

/** * 使用异或运算（最优解） * 步骤： * 1. 初始化结果变量为0（因为 0 ^ a = a）。 * 2. 遍历数组，对每个元素执行异或操作。 * 3. 由于异或性质，出现两次的数字相互抵消，最终结果即为只出现一次的数字。 * 时间复杂度：O(n)，仅一次遍历。 * 空间复杂度：O(1)，只使用一个变量。 */varsingleNumber=function(nums){letresult=0;// 初始化为0，不影响异或结果// 遍历数组，累加异或for(letnumofnums){result^=num;// 等价于 result = result ^ num}// 示例说明：假设 nums = [4,1,2,1,2]// 初始 result = 0// 步骤1: result = 0 ^ 4 = 4// 步骤2: result = 4 ^ 1 = 5// 步骤3: result = 5 ^ 2 = 7// 步骤4: result = 7 ^ 1 = 6// 步骤5: result = 6 ^ 2 = 4// 最终返回 4，即目标数字returnresult;};

5. 各实现思路的复杂度、优缺点对比表格

6. 总结

6.1 通用解题模板或思路

此类“找出唯一出现次数不同的元素”问题，通用解题模式包括：

• 哈希表计数：适用于元素频率统计，是前端处理数据的常见方法（如统计用户行为）。
• 位运算：当其他元素出现偶数次时，异或是王牌解法；对于奇数次，可结合位掩码扩展。
• 数学方法：利用和、差、积等性质，但需注意数值范围。
• 排序后比较：但时间复杂度 O(n log n)，不推荐用于线性要求场景。

在前端开发中，这些思路可应用于状态管理、数据去重、性能优化等场景，例如在 Vue/React 中处理大型数组时，异或运算能高效找出差异项。

6.2 LeetCode中类似题目推荐

• LeetCode 137. 只出现一次的数字 II：元素出现三次，找出一次的元素。需用位运算或数学进阶。
• LeetCode 260. 只出现一次的数字 III：两个元素出现一次，其余出现两次。需异或后分组处理。
• LeetCode 268. 缺失数字：从 0 到 n 的序列中找出缺失数。可用异或或求和。
• LeetCode 389. 找不同：字符串中找多余字符。本质相同，可用异或或哈希表。