[TOC]
本人参加阿里的电话面试时就被问及数组去重的问题，当时我给出了两个答案：
* 一个是循环与indexOf()方法结合；
* 一个是利用es6的Set集合特性；
但是似乎面试官并不满意，至今也不清楚面试官心目中的答案是啥？？
这段代码是下文测试性能使用的，后面会用到，随机生成一个长度为10万的数组，元素跨度是1万。
```
function generateRandomArray () {
let arr = []
let i = 100000
while(i >= 0){
arr.push(Math.ceil(Math.random() * 10000))
i--
}
return arr
}
```
# 方法1：单层循环+indexOf
循环可以使用for或者forEach
## 思路
循环数组，每次循环时判断当前的数组元素是否存在于新数组？如果不存在，则将元素push到新数组
## 实现
```
function distinct1(array) {
let newArr = []
for (let i = 0, length = array.length; i < length; i++) {
if (newArr.indexOf(array[i]) === -1) {
newArr.push(array[i])
}
}
return newArr
}
let array = [2, 1, 2, 4, 3, 5, 3]
console.dir(distinct1(array))
```
```
function distinct2(array) {
let newArr = []
array.forEach(item => {
if (newArr.indexOf(item) === -1) {
newArr.push(item)
}
})
return newArr
}
let array = [2, 1, 2, 4, 3, 5, 3]
console.dir(distinct2(array))
```
## 性能测试
```
let start = Date.now()
distinct1(generateRandomArray()) // distinct2(generateRandomArray())
let end = Date.now()
console.log(end - start) // chrome 第一个290ms 第二个270ms
```
只有一层循环，性能相对来说还可以
# 方法2：filter+indexOf
## 实现
```
function distinct(array) {
return array.filter((item, index) => {
return array.indexOf(item, index + 1) === -1
})
}
let array = [2, 1, 2, 4, 3, 5, 3]
console.dir(distinct(array))
```
## 性能
如果忽略其他因素，只从代码简介度和易读性来说，这个代码确实是很好的，也确实体现了对js的掌握程度。
但是，从其他方面来说，这个代码是否就真的是很好的呢？作为一个追求完美的“猿”，效率恐怕是我最在意的东西了。
```
let start = Date.now()
distinct(generateRandomArray())
let end = Date.now()
console.log(end - start) // chrome 1176ms
```
这个效率，嗯，是很一般的。
我们看代码也不难得出这个结论，filter的效率是n，indexOf的效率是n，两个嵌套，那么效率就是n平方了
***
Tip：
上面生成的随机数数组跨度是1万，那么为什么要有加跨度这个限制呢？因为在试验中发现：
如果数组元素跨度越小，该方法的执行速度就越快；反之越慢。那这是为什么呢？
其实是因为indexOf的机制造成的。indexOf的实现是从你规定的位置开始往后找，找到第一个就停下来。所以很明显：如果跨度越小，呢么出现重复数字的几率就越高，那么久越有可能很快有结果返回，所以跨度越小就会越接近n的效率。
现在如果把数组改成顺序数组，也就是没有重复元素的数组，对其进行去重，看看性能又会如何？
```
let arr = []
let i = 100000
while(i >= 0) {
arr.push(i)
i--
}
```
测试后运行结果是13097ms左右，这才是真正的n平方的效率，之前的1176ms和这个不是一个数量级都。
***
# 方法3：数字下标
**注意：仅适用于元素全为数字的数组**
## 思路
如果数组元素都是数字的话，我们可以使用数字对应下标的方法来进行去重。
比如说：一个数组是：`arr1=[1, 3, 3, 3, 5, 6]`，那么我们就新开一个数组arr2，arr2的值就是`[1,1, , , 1, 1]`
也就是说：只要arr1中出现过的值，我就在arr2中找到对应的下标，并且赋值为1
## 实现
```
function distinct4(array) {
let temp = []
array.forEach(item => {
temp[item] = 1
})
let newArr = []
temp.forEach((item, index) => {
if (item === 1) {
newArr.push(index)
}
})
return newArr
}
let array = [2, 1, 2, 4, 3, 5, 3]
console.log(distinct4(array))
```
## 性能
```
let start = Date.now()
distinct4(generateRandomArray())
let end = Date.now()
console.log(end - start) // chrome 13ms
```
执行结果13ms左右，这个结果效率的差距不是一般的大！
从代码分析，都只有一层循环，那么效率就是O(n)了
# 方法4：sort+filter
## 实现
```
function distinct5(array) {
return array.sort((a, b) => {
return a - b
}).filter((item, index) => {
return item !== array[index - 1]
})
}
let array = [2, 1, 2, 4, 3, 5, 3]
console.log(distinct5(array))
```
## 性能
```
let start = Date.now()
distinct5(generateRandomArray())
let end = Date.now()
console.log(end - start) // chrome 65ms
```
执行结果65ms左右，可以产出这个性能也还算可以（对比第一种和第二种）
# 方法5：filter+object
## 实现
```
function unique (array) {
let obj = {}
return array.filter(item => {
return obj.hasOwnProperty(item) ? false : obj[item] = true
})
}
```
## 性能
26ms左右
# 方法6：filter+Map
## 实现
```
function unique (array) {
let map = new Map()
return array.filter(item => !map.has(item) && map.set(item, 1))
}
```
## 性能
26ms左右
# 方法7：Set集合
## 思路
es6中的Set集合特点是：元素无序，元素不能重复
## 实现
```
function distinct6(array) {
return Array.from(new Set(array))
}
let array = [2, 1, 2, 4, 3, 5, 3]
console.log(distinct6(array))
```
或者这样
```
let unique = array => [...new Set(array)]
```
## 性能
```
let start = Date.now()
distinct6(generateRandomArray())
let end = Date.now()
console.log(end - start) // chrome 28ms
```
效率还是相当高的，和方法3相差无几。并且它没有数据类型的限制和方法3相比
# 总结对比
## 方法1：单层循环+indexOf
优点：
* 效率还行
* 实现简单
* 适用范围广
缺点：
* 逼格不够高
## 方法2：filter+indexOf
优点：
* 简单明了
* 一定程度上可以看出对js的掌握程度
* 适用范围广
缺点：
* 效率非常慢，尤其是在重复元素少的情况下
## 方法3：数字下标
优点：
* 效率极高
* 逼格高
缺点：
* 适用范围小（仅限于数字数组）
* 不容易想到（面试的时候可以来这个）
## 方法4：sort+filter
优点：
* 效率还行
* 适用范围广
缺点：
## 方法5, 6, 7： filter+object filter+map Set
优点：
* 效率极高
* 适用范围广
* 逼格高
