數組去重，是一個老生常談的問題了，在各廠的面試中也會有所提及，接下來就來細數一下各種數組去重的方式吧；

對于以下各種方式都統一命名為 unique，公用代碼如下：

// 生成一個包含100000個[0,50000)隨機數的數組
var arr = [];
for(var i = 0; i < 100000; i++) {arr.push(Math.floor(Math.random() * 50000));
}
Array.prototype.unique = function() { // 算法 };
console.log(arr.unique());  // 一個已經去重的數組
復制代碼

1、雙重遍歷

雙重遍歷的實現主要是通過兩次遍歷的對比，生成一個新的，不含重復數據的數組；

其實現方式有如下兩種：

/** 第一種實現方式：* 對數組的每個元素在推入新數組之前與新數組中每個元素比較，如果沒有相同值則推入*/
Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');var newArray = [], isRepeat;for(var i = 0, length = this.length; i < length; i++) {isRepeat = false;for(var j = 0, newLength = newArray.length; j < newLength; j++) {if(this[i] === newArray[j]) {isRepeat = true;break;}}if(!isRepeat) newArray.push(this[i]);}return newArray;
};
/** 第二種實現方式* 將數組的每個元素與其后面所有元素做遍歷對比，若有相同的值，則不推入新數組，*/
Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');var newArray = [], isRepeat;for(var i = 0, length = this.length; i < length; i++) {isRepeat = false;for(var j = i + 1; j < length; j++) {if(this[i] === this[j]) {isRepeat = true;break;}}if(!isRepeat) newArray.push(this[i]);}return newArray;
};// 實測耗時
// 方式一：2372 ms
// 方式二：4025 ms
復制代碼

2、Array.prototype.indexOf()

通過 indexOf 方法查詢值在數組中的索引，并通過對索引的判斷來實現去重；

主要實現方式有下面兩種：

/*** 第一種實現方式* 結合數組的 filter 方法，將相同值的第一個合并到一個新的數組中返回* indexOf 檢測到的索引為出現當前值的第一個位置* 若 indexOf 檢測到的索引和當前值索引不相等則說明前面有相同的值*/
Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');return this.filter(function(item, index, array) {return array.indexOf(item) === index;});
};
/*** 第二種實現方式* 對數組進行遍歷，并將每個元素在新數組中匹配* 若新數組中無該元素，則插入*/
Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');var newArray = [];this.forEach(function(item) {if(newArray.indexOf(item) === -1) newArray.push(item);});return newArray;
};// 實測耗時
// 方式一：3972 ms
// 方式二：2650 ms
復制代碼

3、Array.prototype.sort()

sort 方法可對數組進行排序，此時相同的值就會被排到一起，然后通過相鄰元素比較就可知是否有相同值了；

舉個栗子：

/*** 第一種實現方式* 先將數組通過 sort 排序* 再遍歷數組，將每個元素與其前面一個元素比較* 若值不同則表示該元素第一次出現，則插入到新數組*/
Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');var newArray = [];this.sort();for(var i = 0, length = this.length; i < length; i++) {if(this[i] !== this[i - 1]) newArray.push(this[i]);}return newArray;
};
/*** 第二種實現方式* 先將數組通過 sort 排序* 再遍歷數組，將每個元素與插入到新數組中的最后一個元素比較* 若值不同則表示該元素第一次出現，則插入到新數組*/
Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');var newArray = [];this.sort();for(var i = 0, length = this.length; i < length; i++) {if(this[i] !== newArray[newArray.length - 1]) newArray.push(this[i]);}return newArray;
};// 實測耗時
// 方式一：105 ms
// 方式二：112 ms
復制代碼

由于方式二在每次比較的時候需要重新計算一次 newArray.length 故會稍微比方式一慢一點；

3、Array.prototype.includes(searchElm, fromIndex)

該方法判斷數組中是否存在指定元素

參數：

• searchElm：需要查找的元素
• fromIndex：開始查找索引位置（若未負值，則從 array.length - fromIndex 位置開始查找

返回值：

• Boolean：數組中是否存在該元素

/*** 實現方式* 遍歷數組，通過 includes 判斷每個值在新數組中是否存在* 若不存在，則將值插入到新數組中*/
Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');var newArray = [];this.forEach(function(item) {if(!newArray.includes(item)) newArray.push(item);});return newArray;
};// 實測耗時：2597 ms
復制代碼

4、Array.prototype.reduce()

/*** 實現方式* 先將數組進行排序* 然后利用 reduce 迭代和累加的特性，將符合要求的元素累加到新數組并返回*/
Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');return this.sort().reduce(function(newArr, curr) {if(newArr[newArr.length - 1] !== curr) newArr.push(curr);return newArr;}, []);
};// 實測耗時：127 ms
復制代碼

5、對象的鍵值對

利用對象的 key 不能重復的特性來去重； 之前看到有人使用對象的鍵值對去重的時候，直接將數組的每個值設置為對象的 key，value 都為1，每出現一個相同的值時就 value++，這樣既可以去重，又可以知道對應的值出現的次數，例如：

var array = ['a', 'b', 'c', 'a', 'a', 'c'];
var newArr = [], obj = {};
array.forEach(function(item) {if(obj[item]) {obj[item]++;} else {obj[item] = 1;newArr.push(item);}
});
console.log(newArr); // ["a", "b", "c"]
console.log(obj);    // {a: 3, b: 1, c: 2}
復制代碼

咋一看好像很完美，可是仔細一想，會發現有以下幾點原因：

• 若數組的值中出現了隱式類型轉換成字符串后相等的值，則無法區分，例如 '1' 和 1；
• 若數組中的值有對象，寫成 key 之后都是 [object Object]，無法區分；

解決方案：

若元素值的類型為 object，則通過 JSON.stringify 方法進行轉換；

Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');var newArr = [], obj = {};this.forEach(function(item) {if(!obj[typeof item + JSON.stringify(item)]) {obj[typeof item + JSON.stringify(item)] = 1;newArr.push(item);}});return newArr;
};// 實測耗時：142 ms
復制代碼

6、Set

Set 對象的特性就是其中的值是唯一的，可利用該特性很便捷的處理數組去重的問題；

/*** 實現方式一* 將數組轉換成 Set 對象* 通過 Array.from 方法將 Set 對象轉換為數組*/
Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');var set = new Set(this);return Array.from(set);
};// 實測耗時：45 ms/*** 實現方式二* 將數組轉換成 Set 對象* 通過 Array.from 方法將 Set 對象轉換為數組*/
Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');return [...new Set(this)];
};// 實測耗時：65 ms
復制代碼

由以上耗時結果可以看出：

• filter, forEach 等方法都會對全數組進行遍歷；
• indexOf, for+break, includes 等方法會對數組遍歷，在滿足條件的地方跳出遍歷