前端JavaScript算法找出只出现一次的数字
作者:异步漫步时间:2026-10-25 14:59:20浏览:178
本文介绍如何在JavaScript中高效解决“只出现一次的数字”算法题。通过对比Map计数法与异或运算法,重点解析如何利用位运算特性在O(n)时间复杂度和O(1)空间复杂度下找出唯一元素,提供完整代码实现与原理说明。
题目:只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1] 输出: 1
示例 2:
输入: [4,1,2,1,2] 输出: 4
解:
首个思路是利用 map 数据结构求解,该方案时间复杂度为 O(n),符合线性要求,但空间复杂度为 O(n);下文方法二将阐述如何降低空间消耗。
解法一:用 map 来解:
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
let map = new Map();
for(let i = 0; i<nums.length;i++){
if(map.has(nums[i])){
map.set(nums[i],map.get(nums[i])+1);
}else{
map.set(nums[i],1)
}
}
for(let [key,value] of map.entries()){
if(value===1){
return key
}
}
};

解法二:用 异或 解
核心在于理解如何做到:不使用额外空间来实现
即需在数组原数据进行操作,异或运算可达成此目标;
异或(eor)属逻辑运算。相同数值异或结果为0;不同数值异或结果为1;非零数与0异或等于其本身;
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
for (var i = 1; i < nums.length; i++) {
nums[0] = nums[0] ^ nums[i]; // 把所有的元素都异或到nums[0]上。
}
return nums[0];
};

以上为前端JavaScript算法找出只出现一次的数字的详细信息,更多JavaScript算法只出现一次数字的内容请查阅本站其他文章!
作者最新文章
D3.js 比例尺与坐标轴的配置详解
2026-11-05 16:54:46
JavaScript怎么遍历对象的Symbol键和不可枚举属性
2026-11-05 13:13:39
封装一个健壮的JS字符串判空工具函数
2026-11-05 12:16:14
JavaScript合并数组的三种常用方法:concat、扩展运算符与push
2026-11-05 11:22:29
JavaScript立即执行函数(IIFE)是什么及基本语法
2026-11-05 10:51:19
