给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
算法分析
1、遍历数组中的每一个元素
2、如果当前元素是新出现的,则将它添加到列表中
3、如果当前元素已经存在列表中,则从列表中删除它
JavaScript Code:
function singleNumber(nums){
let items = [];
for(let num of nums) {
let index = items.indexOf(num);
if(index != -1) {
items.splice(index, 1);
} else {
items.push(num);
}
}
return items.pop();
}
上述的 JavaScript 实现虽然实现了功能,但需要一个额外的数组来存储 nums 数组中的元素,此外除了遍历原始的 nums 数组外,我们还需要遍历 items 数组,判断当前的元素是否已经存在列表中,这样导致该算法的时间复杂度为 O(n2) 。
为了减少列表操作算法的时间复杂度,我们可以使用哈希集来避免每次查找元素是否存在需要的 O(n) 时间。
算法分析
1、遍历数组中的每个元素
2、判断哈希集中是否有当前的元素
3、如果不包含当前的元素,则将当前元素添加到集合中
4、循环结束后获取哈希集中的元素
JavaScript Code:
function singleNumber(nums){
const set = new Set();
for(let num of nums) {
if(set.has(num)){
set.delete(num);
} else {
set.add(num);
}
}
return [...set][0];
}
使用哈希集的方式,虽然减少列表操作算法的时间复杂度,但仍然需要开辟额外的空间来存储 nums 中的元素。下面我们来介绍另一种算法,即不使用额外空间来实现同样的功能。
在介绍具体解法时,我们先来了解一下异或运算,其运算规则如下:
1 ⊕ 1 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
0 ⊕ 0 = 0
此外,异或运算有以下几个特点:
1、一个数与 0 进行异或运算等于它本身:a ⊕ 0 = a;
0000 1111 //a=15
⊕ 0000 0000
------------
0000 1111
2、一个数与它本身进行异或运算等于 0:a ⊕ a = 0;
0000 1111 //a=15
⊕ 0000 1111 //a=15
------------
0000 0000
3、异或运算满足加法交换律和结合律:a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b。
a ⊕ b ⊕ a
0000 1111 //a=15
⊕ 0000 1000 //b=8
------------
0000 0111 //a ⊕ b的结果
⊕ 0000 1111 //a=15
------------
0000 1000 // a ⊕ b ⊕ a的结果
因此基于以上异或运算的特点,将所有数字按照顺序做异或运算,最后剩下的结果即为唯一的数字。
Java Code:
public int singleNumber(int[] nums) {
int ans = 0;
for(int num: nums) {
ans ^= num;
}
return ans;
}
JavaScript Code:
function singleNumber(nums) {
let ans = 0;
for(const num of nums) {
ans ^= num;
}
return ans;
}
欢迎小伙伴们订阅前端全栈修仙之路,及时阅读 Angular、TypeScript、Node.js/Java和Spring技术栈最新文章。