4. 数组去重 | 砥砺前行

[TOC]

写作不易，Star是最大鼓励，感觉写的不错的可以给个Star⭐，请多多指教。Github地址。

原数组如下：

let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {}, {}, 'abc', 'abc', undefined, undefined, NaN, NaN];

1. ES6的Set数据结构

ES6提供了新的数据结构Set。它类似于数组，但是成员的值都是唯一的，没有重复的值。Set本身是一个构造函数，用来生成Set数据结构。

console.log([...new Set(originalArray)]); // [ 1, '1', 2, true, 'true', false, null, {}, {}, 'abc', undefined, NaN ]
// [ 1, '1', 2, true, 'true', false, null, {}, {}, 'abc', undefined, NaN ]
console.log(Array.from(new Set(originalArray)));

1
2
3

Set并不是真正的数组，上面例子中的Array.from和扩展运算符...都可以将Set数据结构，转换成最终的结果数组。

这是最简单快捷的去重方法，但是细心的同学会发现，这里的 {} 没有去重。可是又转念一想，2个空对象的地址并不相同，所以这里并没有问题，结果ok。

Set缺点

Set无法对引用类型的元素去重。

const mySet = new Set();
mySet.add(1);
mySet.add(1);
mySet.add({name: 'lisi', age: 10});
mySet.add({name: 'lisi', age: 10});

console.log(mySet); // Set { 1, { name: 'lisi', age: 10 }, { name: 'lisi', age: 10 } }

1
2
3
4
5
6
7

2. Map的has方法

把原数组的每一个元素作为key存到Map中。由于Map中不会出现相同的key值，所以最终得到的就是去重后的结果。

// Map的key
let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {}, {}, 'abc', 'abc', undefined, undefined, NaN, NaN];
const resultArr = [];
const map = new Map();
originalArray.forEach(item => {
    // 没有该key值
    if (!map.has(item)) {
        map.set(item, true);
        resultArr.push(item);
    }
});

console.log(resultArr); // [ 1, '1', 2, true, 'true', false, null, {}, {}, 'abc', undefined, NaN ]

1
2
3
4
5
6
7
8
9
10
11
12
13

3. indexOf和includes

indexOf

let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {}, {}, 'abc', 'abc', undefined, undefined, NaN, NaN];
const resultArr = [];

originalArray.forEach(item => {
    // resultArr中没有该item的值
    if (resultArr.indexOf(item) < 0) {
        resultArr.push(item);
    }
});

console.log(resultArr); // [ 1, '1', 2, true, 'true', false, null, {}, {}, 'abc', undefined, NaN, NaN ]

1
2
3
4
5
6
7
8
9
10
11

需要注意：indexOf并不没处理NaN。

includes

let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {}, {}, 'abc', 'abc', undefined, undefined, NaN, NaN];
const resultArr = [];

originalArray.forEach(item => {
    // resultArr中没有该item的值
    if (!resultArr.includes(item)) {
        resultArr.push(item);
    }
});

console.log(resultArr); // [1, '1', 2, true, 'true', false, null, {}, {}, 'abc', undefined, NaN]

1
2
3
4
5
6
7
8
9
10
11

includes处理了NaN，结果ok。

4. sort

// sort
let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {}, {}, 'abc', 'abc', undefined, undefined, NaN, NaN];
// 对原数组进行排序
originalArray.sort();
// 将排序后的第一项放到结果数组中
const resultArr = [originalArray[0]];
for (let i = 1; i < originalArray.length; i++) {
    if (originalArray[i] !== resultArr[resultArr.length - 1]) {
        resultArr.push(originalArray[i]);
    }
}

console.log(resultArr); // [1, "1", 2, NaN, NaN, {}, {}, "abc", false, null, true, "true", undefined]

1
2
3
4
5
6
7
8
9
10
11
12
13

需要注意，这种方法同样没有处理NaN。

5. 双层for循环 + splice

双层循环，外层循环遍历原数组，内层从i+1开始遍历比较，相同时删除这个值。

// 双层 for 循环 + splice
let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {}, {}, 'abc', 'abc', undefined, undefined, NaN, NaN];
for (let i = 0; i < originalArray.length - 1; i++) {
    for (let j = i + 1; j < originalArray.length - 1; j++) {
        if (originalArray[i] === originalArray[j]) {
            originalArray.splice(j, 1);
            // j--;
        }
    }
}

console.log(originalArray); // [1, "1", 2, true, "true", false, null, {…}, {…}, "abc", undefined, NaN, NaN]

1
2
3
4
5
6
7
8
9
10
11
12

splice方法会修改原数组，所以这里我们并没有新开空数组去存储，最终输出的是修改之后的原数组。但同样的没有处理NaN。

6. 原始去重

// 原始去重
let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {}, {}, 'abc', 'abc', undefined, undefined, NaN, NaN];
let resArr = [originalArray[0]];
for (let i = 1; i < originalArray.length; i++) {
    let isRepeat = false;
    for (let j = 0; j < resArr.length; j++) {
        // 如果结果数组中已经存在该值，跳出内层循环
        if (originalArray[i] === resArr[j]) {
            isRepeat = true;
            break;
        }
    }
    if (!isRepeat) {
        resArr.push(originalArray[i]);
    }
}

console.log(resArr); // [1, "1", 2, true, "true", false, null, {}, {}, "abc", undefined, NaN, NaN]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这是最原始的去重方法，很好理解，但写法繁琐。同样的没有处理NaN。

7. ES5的reduce

// reduce
let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {}, {}, 'abc', 'abc', undefined, undefined, NaN, NaN];
let resArr = [];

resArr = originalArray.reduce((acc, cur) => {
    return acc.includes(cur) ? acc : [...acc, cur];
}, []);

console.log(resArr); // [ 1, '1', 2, true, 'true', false, null, {}, {}, 'abc', undefined, NaN ]

1
2
3
4
5
6
7
8
9

8. 对象的属性(不推荐使用)

每次取出原数组的元素，然后在对象中访问这个属性，如果存在就说明重复。

let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {}, {}, 'abc', 'abc', undefined, undefined, NaN, NaN];
let resArr = [];
const obj = {};
for(let i = 0; i < originalArray.length; i++) {
    if(!obj[originalArray[i]]){
        resultArr.push(originalArray[i]);
        obj[originalArray[i]] = 1;
    }
}
obj = null; // 对象销毁，释放内存
console.log(resultArr);
// [1, 2, true, false, null, {…}, "abc", undefined, NaN]

1
2
3
4
5
6
7
8
9
10
11
12

但这种方法有缺陷。从结果看，它貌似只关心值，不关注类型。还把 {} 给处理了，但这不是正统的处理办法，所以不推荐使用。

let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {}, {}, 'abc', 'abc', undefined, undefined, NaN, NaN];
let resArr = [];
let obj = {};

for (let i = 0; i < originalArray.length; i++) {
    let item = originalArray[i];
    if (obj[item]) {
        originalArray[i] = originalArray[originalArray.length - 1];
        originalArray.length--;
        i--;
        continue;
    }
    obj[item] = item;
}

obj = null;

console.log(originalArray); // [1, NaN, NaN, 2, true, undefined, false, false, null, null, {…}, undefined, "abc"]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

9. filter + hasOwnProperty

filter 方法会返回一个新的数组，新数组中的元素，通过 hasOwnProperty 来检查是否为符合条件的元素。

const obj = {};
const resultArr = originalArray.filter(function (item) {
    return obj.hasOwnProperty(typeof item + item) ? false : (obj[typeof item + item] = true);
});

console.log(resultArr);
// [1, "1", 2, true, "true", false, null, {…}, "abc", undefined, NaN]

1
2
3
4
5
6
7

这貌似是目前看来最完美的解决方案了。这里稍加解释一下：

hasOwnProperty 方法会返回一个布尔值，指示对象自身属性中是否具有指定的属性。
typeof item + item 的写法，是为了保证值相同，但类型不同的元素被保留下来。例如：第一个元素为 number1，第二第三个元素都是 string1，所以第三个元素就被去除了。
obj[typeof item + item] = true 如果 hasOwnProperty 没有找到该属性，则往 obj 里塞键值对进去，以此作为下次循环的判断依据。
如果 hasOwnProperty 没有检测到重复的属性，则告诉 filter 方法可以先积攒着，最后一起输出。

看似完美解决了我们源数组的去重问题，但在实际的开发中，一般不会给两个空对象给我们去重。所以稍加改变源数组，给两个空对象中加入键值对。

let originalArray = [1, '1', '1', 2, true, 'true', false, false, null, null, {a: 1}, {a: 2}, 'abc', 'abc', undefined, undefined, NaN, NaN];

然后再用 filter + hasOwnProperty 去重。然而，结果竟然把 {a: 2} 给去除了！！！这就不对了。所以，这种方法有点去重过头了，也是存在问题的。特别注意：字符串与对象拼接。

'1' + {name: 'lisi'} // "1[object Object]"

10. lodash中的`_.uniq`

console.log(_.uniq(originalArray));

// [1, "1", 2, true, "true", false, null, {…}, {…}, "abc", undefined, NaN]

1
2
3

然后，我在好奇心促使下，看了它的源码，指向了baseUniq文件，它的源码如下：

function baseUniq(array, iteratee, comparator) {
  let index = -1
  let includes = arrayIncludes
  let isCommon = true

  const { length } = array
  const result = []
  let seen = result

  if (comparator) {
    isCommon = false
    includes = arrayIncludesWith
  }
  else if (length >= LARGE_ARRAY_SIZE) {
    const set = iteratee ? null : createSet(array)
    if (set) {
      return setToArray(set)
    }
    isCommon = false
    includes = cacheHas
    seen = new SetCache
  }
  else {
    seen = iteratee ? [] : result
  }
  outer:
  while (++index < length) {
    let value = array[index]
    const computed = iteratee ? iteratee(value) : value

    value = (comparator || value !== 0) ? value : 0
    if (isCommon && computed === computed) {
      let seenIndex = seen.length
      while (seenIndex--) {
        if (seen[seenIndex] === computed) {
          continue outer
        }
      }
      if (iteratee) {
        seen.push(computed)
      }
      result.push(value)
    }
    else if (!includes(seen, computed, comparator)) {
      if (seen !== result) {
        seen.push(computed)
      }
      result.push(value)
    }
  }
  return result
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

`_.uniqBy`

_.uniqBy方法可以通过指定 key，来专门去重对象列表。

_.uniqBy([{ 'x': 1 }, { 'x': 2 }, { 'x': 1 }], 'x');
// => [{ 'x': 1 }, { 'x': 2 }]

1
2

`_.uniqWith`

_.uniqWith方法可以完全地给对象中所有的键值对，进行比较。

import _ from 'lodash';
<script>
var objects = [{ 'x': 1, 'y': 2 }, { 'x': 2, 'y': 1 }, { 'x': 1, 'y': 2 }];
_.uniqWith(objects, _.isEqual);
</script>

//=> [{ 'x': 1, 'y': 2 }, { 'x': 2, 'y': 1 }]

1
2
3
4
5
6
7

其中， _.isEqual(value,other)用于执行深比较来确定两者的值是否相等。_.uniqWith()做去重处理。

参考文档

「前端面试题系列8」数组去重(10 种浓缩版)

← 3. 数组方法总结与实现 5. call、apply以及bind模拟实现→

# 1. ES6的Set数据结构

# Set缺点

# 2. Map的has方法

# 3. indexOf和includes

# indexOf

# includes

# 4. sort

# 5. 双层for循环 + splice

# 6. 原始去重

# 7. ES5的reduce

# 8. 对象的属性(不推荐使用)

# 9. filter + hasOwnProperty

# 10. lodash中的_.uniq

# _.uniqBy

# _.uniqWith

# 参考文档

1. ES6的Set数据结构

Set缺点

2. Map的has方法

3. indexOf和includes

indexOf

includes

4. sort

5. 双层for循环 + splice

6. 原始去重

7. ES5的reduce

8. 对象的属性(不推荐使用)

9. filter + hasOwnProperty

10. lodash中的`_.uniq`

`_.uniqBy`

`_.uniqWith`

参考文档