JS数组去重的那些事

JS的数组去重是一道面试高频题,在团队最近一次的Code Review也遇到了相关问题,在此记录一下。

1. 普通数组

对于普通数组,我们很容易就能写出下面这种代码:

1
2
3
4
5
6
7
8
9
let numbers = [1, 2, 3, 3, 2, 1];
for(let i=0;i<numbers.length-1;i++) {
for(let j=i+1;j<numbers.length;j++) {
if(numbers[i] === numbers[j]) {
number.splice(j, 1);
j--;
}
}
}

思路也很简单,就是使用双重for循环去遍历数组,时间复杂度为O(n2)。那么有没有稍微优雅一点的方法呢?看下面代码:

1
2
3
4
5
6
7
let numbers = [1, 2, 3, 3, 2, 1];
let res = []
for(let i=0;i<numbers.length-1;i++) {
if(!res.includes(numbers[i])) {
res.push(numbers[i])
}
}

是不是看起来要比之前的代码简短点?这里开辟了一个新的数组res,但数组的查找是O(n)的复杂度,所以这里的复杂度也是O(n2)。那有没有效率更高一点的方法呢?看下面代码:

1
2
3
4
5
6
7
8
let numbers = [1, 2, 3, 3, 2, 1];
let hash = {};
for(let i=0;i<numbers.length-1;i++) {
if(!hash[numbers[i]]) {
hash[numbers[i]] = true;
}
}
numbers = Object.keys(hash);

这里把数组换成了对象,对象的查找是O(1)的时间复杂度,所以这里的时间复杂度为O(n)。那么有没有更短一点的方法了呢?在ES6中我们可以使用Set数据结构来去重:

1
2
let numbers = [1, 2, 3, 3, 2, 1];
numbers = [...new Set(numbers)];

是不是更简洁呢?而且使用Set数据结构去重效率也更高。那既然上了ES6了,有没有其他方法呢?看下面代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 使用filter,去重的本质就是按照数据唯一的特点筛选数组,filter刚好可以筛选,所以与去重的行为是一致的
let numbers = [1, 2, 3, 3, 2, 1];
numbers.filter((item, index, currentArr) => currentArr.indexOf(item) === index); // 时间复杂度为O(n2)

// 在filter的基础上使用空间换时间的思想提高效率
let numbers = [1, 2, 3, 3, 2, 1];
let hash = {};
numbers.filter(item => hash[item] ? false : hash[item] = true); // 时间复杂度为O(n)

// 使用reduce去重,改自MDN https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/Reduce
let numbers = [1, 2, 3, 3, 2, 1];
numbers.reduce((pre, cur) => pre.includes(cur) ? pre : [...pre, cur], []); // 时间复杂度为O(n2)

// 在reduce的基础上使用空间换时间的思想提高效率
let numbers = [1, 2, 3, 3, 2, 1];
let hash = {};
numbers.reduce((pre, cur) => (hash[cur] || (hash[cur] = true) && pre.push(cur), pre), []); // 时间复杂度为O(n)

2. 复杂数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 使用filter
let numbers = [{user: 1}, {user: 1}, {user: 2}, {user: 2}];
numbers.filter((itemObj, index, currentArr) => currentArr.findIndex(itemObj2 => itemObj2.user === itemObj.user) === index); // 时间复杂度为O(n2)

// 在filter的基础上使用空间换时间的思想提高效率
let numbers = [{user: 1}, {user: 1}, {user: 2}, {user: 2}];
let hash = {};
numbers.filter(item => hash[item.user] ? false : hash[item.user] = true); // 时间复杂度为O(n)

// 使用reduce去重
let numbers = [{user: 1}, {user: 1}, {user: 2}, {user: 2}];
numbers.reduce((pre, cur) => pre.find(item => item.user === cur.user) ? pre : [...pre, cur], []); // 时间复杂度为O(n2)

// 在reduce的基础上使用空间换时间的思想提高效率
let numbers = [{user: 1}, {user: 1}, {user: 2}, {user: 2}];
let hash = {};
numbers.reduce((pre, cur) => (hash[cur.user] || (hash[cur.user] = true) && pre.push(cur), pre), []); // 时间复杂度为O(n)
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2019-2021 musi

请我喝杯咖啡吧~

支付宝
微信