如何答一道惊艳面试官的数组去重问题？

数组去重应该是面试?必考?问题之一。

尽管它是一道并不复杂的问题，但是也能看出面试者的?广度和深度?，还有考虑问题的全面性。

实际开发中我们应该选择哪种方式数组去重，本文告诉你。

你以为的不肯定你以为，面试官不只是让你去重一个数组，他想知道的有点多，包括你的思想。

当面试官问到时怎样答复？

首先:我知道多少种去重方式

双层 for 循环

functiondistinct(arr){for(leti=0, len=arr.length; i

思想: 双重 for 循环是比较笨拙的方法，它实现的原理很简单：先定义一个包含原始数组第一个元素的数组，而后遍历原始数组，将原始数组中的每个元素与新数组中的每个元素进行比对，假如不重复则增加到新数组中，最后返回新数组；由于它的时间复杂度是?O(n^2)?，假如数组长度很大，?效率会很低?。

Array.filter() 加 indexOf

functiondistinct(a, b){letarr = a.concat(b);returnarr.filter((item, index)=>{returnarr.indexOf(item) === index? ? })}复制代码

思想: 利用indexOf检测元素在数组中第一次出现的位置能否和元素现在的位置相等，假如不等则说明该元素是重复元素

Array.sort() 加一行遍历冒泡(相邻元素去重)

functiondistinct(array){varres = [];varsortedArray =array.concat().sort();varseen;for(vari =0, len = sortedArray.length; i < len; i++) {// 假如是第一个元素或者者相邻的元素不相同if(!i || seen !== sortedArray[i]) {? ? ? ? ? ? res.push(sortedArray[i])? ? ? ? }? ? ? ? seen = sortedArray[i];? ? }returnres;}复制代码

思想: 调用了数组的排序方法?sort()?，V8引擎 的 sort() 方法在数组长度小于等于10的情况下，会使用插入排序，大于10的情况下会使用快速排序(sort函数在我之前高阶函数那篇文章有详细讲解?【JS必知必会】高阶函数详解与实战?)。而后根据排序后的结果进行遍历及相邻元素比对(其实就是一行冒泡排序比较)，假如相等则跳过该元素，直到遍历结束。

ES6 中的 Set 去重

functiondistinct(array){returnArray.from(newSet(array));}复制代码

甚至可以再简化下：

functionunique(array){return[…newSet(array)];}复制代码

还可以再简化下：

letunique =(a) =>[…newSet(a)]复制代码

思想: ES6 提供了新的数据结构 Set，Set 结构的一个特性就是成员值都是唯一的，没有重复的值。(同时请大家注意这个简化过程)

Object 键值对

functiondistinct(array){varobj = {};returnarray.filter(function(item, index, array){returnobj.hasOwnProperty(typeofitem + item) ?false: (obj[typeofitem + item] =true)? ? })}复制代码

这种方法是利用一个空的 Object 对象，我们把数组的值存成 Object 的 key 值，比方?Object[value1] = true?，在判断另一个值的时候，假如 Object[value2]存在的话，就说明该值是重复的,但是最后请注意这里?obj[typeof item + item] = true?没有直接使用?obj[item]?,是由于 由于 123 和 ‘123’ 是不同的，直接使用前面的方法会判断为同一个值，由于?对象的键值只能是字符串?，所以我们可以使用?typeof item + item?拼成字符串作为 key 值来避免这个问题。

而后:讯问面试官具体场景

(假如你考虑的这些和你问的，面试官不以为然，可能自己都没想，随意让你数组去重，可能这个面试官也…)

性能考虑(是想要最快的速度查到数据吗？)

为了测试这些解法的性能，我写了一个测试模版，用来计算数组去重的耗时。 模版代码如下:

// distinct.jsletarr1 =Array.from(newArray(100000), (x, index)=>{returnindex})letarr2 =Array.from(newArray(50000), (x, index)=>{returnindex+index})letstart =newDate().getTime()console.log(‘开始数组去重’)letarr = a.concat(b);functiondistinct(arr){// 数组去重}console.log(‘去重后的长度’, distinct(arr).length)letend =newDate().getTime()console.log(‘耗时’, end – start)复制代码

上面的多种数组去后，计算耗费时间

双重 for 循环 > Array.filter()加 indexOf > Array.sort() 加一行遍历冒泡 > ES6中的Set去重 > Object 键值对去重复

注意:这里只是本人测试的结果，具体情况可能与场景不同，比方排序过的数组直接去重，直接使用冒泡相邻比较性能可能更好。大家也可以自己尝试一下，有问题欢迎一起探讨指出。

兼容性与场景考虑(数组中能否包含对象，NaN等？)

我们要考虑这个数组中能否有null、undefined、NaN、对象假如二者都出现，上面的所有数组去重方法并不是都是适用哦，下面详细说一下。

先说一下 == 和 === 区别

===?严格相等，会比较两个值的类型和值?==?笼统相等，比较时，会先进行类型转换，而后再比较值 想更详细理解转换过程的可以看这篇文章?js 中 == 和 === 的区别

说一下我说的几个类型的相等问题

letstr1 =’123′;letstr2 =newString(‘123’);console.log(str1 == str2);// trueconsole.log(str1 === str2);// falseconsole.log(null==null);// trueconsole.log(null===null);// trueconsole.log(undefined==undefined);// trueconsole.log(undefined===undefined);// trueconsole.log(NaN==NaN);// falseconsole.log(NaN===NaN);// falseconsole.log(/a/==/a/);// falseconsole.log(/a/===/a/);// falseconsole.log({} == {});// falseconsole.log({} === {});// false复制代码

几种去重函数针对带有特殊类型的比照

indexOf 与 Set 的一点说明：

上面代码中?console.log(NaN === NaN); // false?, indexOf 底层使用的是 === 进行判断，所以使用 indexOf 查找不到 NaN 元素

// demo1vararr = [1,2,NaN];arr.indexOf(NaN);// -1复制代码

Set可以去重NaN类型， Set内部认为虽然 NaN === NaN 为 false，但是这两个元素是重复的。

// demo2functiondistinct(array){returnArray.from(newSet(array));}console.log(unique([NaN,NaN]))// [NaN]复制代码

具体去重比较

将这样一个数组按照上面的方法去重后的比较：

vararray = [1,1,’1′,’1′,null,null,undefined,undefined,newString(‘1’),newString(‘1’),/a/,/a/,NaN,NaN];复制代码

方法结果说明

双层 for 循环[1, “1”, null, undefined, String, String, /a/, /a/, NaN, NaN]对象和 NaN 不去重

Array.sort()加一行遍历冒泡[/a/, /a/, “1”, 1, String, 1, String, NaN, NaN, null, undefined]对象和 NaN 不去重 数字 1 也不去重

Array.filter()加 indexOf[1, “1”, null, undefined, String, String, /a/, /a/]对象不去重 NaN 会被忽略掉

Object 键值对去重[1, “1”, null, undefined, String, /a/, NaN]一律去重

ES6中的Set去重[1, “1”, null, undefined, String, String, /a/, /a/, NaN]对象不去重 NaN 去重

内存考虑(去重复过程中，是想要空间复杂度最低吗？)

尽管说对于 V8 引擎，内存考虑已经显得不那么重要了，而且真的数据量很大的时候，一般去重在后端解决了。虽然如此，我们也?不能放过任何一个可以证实自己优秀的?，还是考虑一下，嘿嘿。

以上的所有数组去重方式，应该 Object 对象去重复的方式是时间复杂度是最低的，除了一次遍历时间复杂度为?O(n)?后，查找到重复数据的时间复杂度是?O(1)?，相似散列表，大家也可以使用 ES6 中的 Map 尝试实现一下。

但是对象去重复的空间复杂度是最高的，由于开拓了一个对象，其余的几种方式都没有开拓新的空间，从外表看来，更深入的源码有待探索，这里只是要说明大家在答复的时候也可以考虑到?时间复杂度?还有?空间复杂度?。

另外补充一个?误区?，有的小伙伴会认为?Array.filter()?加?indexOf?这种方式时间复杂度为?O(n)?,其实不是这样，我觉得也是?O(n^2)?。由于?indexOf?函数，源码其实它也是进行 for 循环遍历的。具体实现如下

String.prototype.indexOf = function(s) {for(vari =0; i

补充说明第三方库lodash

lodash 如何实现去重

简单说下?lodash?的?uniq?方法的源码实现。

这个方法的行为和使用 Set 进行去重的结果一致。

当数组长度大于等于?200?时，会创立?Set?并将?Set?转换为数组来进行去重（Set 不存在情况的实现不做分析）。当数组长度小于?200?时，会使用相似前面提到的 双重循环 的去重方案，?另外还会做 NaN 的去重?。

总结

面试时答复面试官的问题，除了你能把代码编出来运行出正确的结果，正确还包含对问题的独到见地,还需要考虑下面的问题：

优化

代码规范

容错性?其实假如是非常难的问题，对你的竞争对手来说，也是难的，关键在于你所表达出的处理问题的思路，甚至通过表达解题思路的方向，以及你考虑问题的全面性，其实不仅仅这一道简单面试题，算法题是如此。我是?koala?，今天这篇先写这么多，一起加油。

通过怎样样的学习，才能成为合格的WEB前台工程师？假如现在的你很迷茫，可以＋web前台扣扣裙：965747894 免费网课在线学习以及问题解答、项目指导服务，配合强大的学习工具，带你完成九大实战项目，经历从零基础到专业前台工程师的完美蜕变。