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