qrcode

加入前端交流群,阿里、腾讯和京东大佬都在的群里

最常见面试算法之只出现1次的数字

一、题目描述

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

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

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

示例 2:

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

二、题解

2.1 列表操作

算法分析

1、遍历数组中的每一个元素

2、如果当前元素是新出现的,则将它添加到列表中

3、如果当前元素已经存在列表中,则从列表中删除它

JavaScript Code:

1
2
3
4
5
6
7
8
9
10
11
12
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) 。

2.2 哈希集(HashSet)

为了减少列表操作算法的时间复杂度,我们可以使用哈希集来避免每次查找元素是否存在需要的 O(n) 时间。

算法分析

1、遍历数组中的每个元素

2、判断哈希集中是否有当前的元素

3、如果不包含当前的元素,则将当前元素添加到集合中

4、循环结束后获取哈希集中的元素

JavaScript Code:

1
2
3
4
5
6
7
8
9
10
11
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 中的元素。下面我们来介绍另一种算法,即不使用额外空间来实现同样的功能。

2.3 按位异或

在介绍具体解法时,我们先来了解一下异或运算,其运算规则如下:

1
2
3
4
1 ⊕ 1 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
0 ⊕ 0 = 0

此外,异或运算有以下几个特点:

1、一个数与 0 进行异或运算等于它本身:a ⊕ 0 = a;

1
2
3
4
  0000 1111 //a=15
⊕ 0000 0000
------------
0000 1111

2、一个数与它本身进行异或运算等于 0:a ⊕ a = 0;

1
2
3
4
  0000 1111 //a=15
⊕ 0000 1111 //a=15
------------
0000 0000

3、异或运算满足加法交换律和结合律:a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b。

1
2
3
4
5
6
7
8
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:

1
2
3
4
5
6
7
public int singleNumber(int[] nums) {
int ans = 0;
for(int num: nums) {
ans ^= num;
}
return ans;
}

JavaScript Code:

1
2
3
4
5
6
7
function singleNumber(nums) {
let ans = 0;
for(const num of nums) {
ans ^= num;
}
return ans;
}

三、参考资源


欢迎小伙伴们订阅全栈修仙之路,及时阅读 TypeScript、Node/Deno、Angular 技术栈最新文章。

qrcode