[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
優點：
* 效率極高
* 適用范圍廣
* 逼格高
