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

對(duì)于以下各種方式都統(tǒng)一命名為 unique，公用代碼如下：

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

1、雙重遍歷

雙重遍歷的實(shí)現(xiàn)主要是通過兩次遍歷的對(duì)比，生成一個(gè)新的，不含重復(fù)數(shù)據(jù)的數(shù)組；

其實(shí)現(xiàn)方式有如下兩種：

/** 第一種實(shí)現(xiàn)方式：* 對(duì)數(shù)組的每個(gè)元素在推入新數(shù)組之前與新數(shù)組中每個(gè)元素比較，如果沒有相同值則推入*/ 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; }; /** 第二種實(shí)現(xiàn)方式* 將數(shù)組的每個(gè)元素與其后面所有元素做遍歷對(duì)比，若有相同的值，則不推入新數(shù)組，*/ 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; };// 實(shí)測(cè)耗時(shí) // 方式一：2372 ms // 方式二：4025 ms 復(fù)制代碼

2、Array.prototype.indexOf()

通過 indexOf 方法查詢值在數(shù)組中的索引，并通過對(duì)索引的判斷來實(shí)現(xiàn)去重；

主要實(shí)現(xiàn)方式有下面兩種：

/*** 第一種實(shí)現(xiàn)方式* 結(jié)合數(shù)組的 filter 方法，將相同值的第一個(gè)合并到一個(gè)新的數(shù)組中返回* indexOf 檢測(cè)到的索引為出現(xiàn)當(dāng)前值的第一個(gè)位置* 若 indexOf 檢測(cè)到的索引和當(dāng)前值索引不相等則說明前面有相同的值*/ 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;}); }; /*** 第二種實(shí)現(xiàn)方式* 對(duì)數(shù)組進(jìn)行遍歷，并將每個(gè)元素在新數(shù)組中匹配* 若新數(shù)組中無該元素，則插入*/ 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; };// 實(shí)測(cè)耗時(shí) // 方式一：3972 ms // 方式二：2650 ms 復(fù)制代碼

3、Array.prototype.sort()

sort 方法可對(duì)數(shù)組進(jìn)行排序，此時(shí)相同的值就會(huì)被排到一起，然后通過相鄰元素比較就可知是否有相同值了；

舉個(gè)栗子：

/*** 第一種實(shí)現(xiàn)方式* 先將數(shù)組通過 sort 排序* 再遍歷數(shù)組，將每個(gè)元素與其前面一個(gè)元素比較* 若值不同則表示該元素第一次出現(xiàn)，則插入到新數(shù)組*/ 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; }; /*** 第二種實(shí)現(xiàn)方式* 先將數(shù)組通過 sort 排序* 再遍歷數(shù)組，將每個(gè)元素與插入到新數(shù)組中的最后一個(gè)元素比較* 若值不同則表示該元素第一次出現(xiàn)，則插入到新數(shù)組*/ 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; };// 實(shí)測(cè)耗時(shí) // 方式一：105 ms // 方式二：112 ms 復(fù)制代碼

由于方式二在每次比較的時(shí)候需要重新計(jì)算一次 newArray.length 故會(huì)稍微比方式一慢一點(diǎn)；

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

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

參數(shù)：

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

返回值：

• Boolean：數(shù)組中是否存在該元素

/*** 實(shí)現(xiàn)方式* 遍歷數(shù)組，通過 includes 判斷每個(gè)值在新數(shù)組中是否存在* 若不存在，則將值插入到新數(shù)組中*/ 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; };// 實(shí)測(cè)耗時(shí)：2597 ms 復(fù)制代碼

4、Array.prototype.reduce()

/*** 實(shí)現(xiàn)方式* 先將數(shù)組進(jìn)行排序* 然后利用 reduce 迭代和累加的特性，將符合要求的元素累加到新數(shù)組并返回*/ 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;}, []); };// 實(shí)測(cè)耗時(shí)：127 ms 復(fù)制代碼

5、對(duì)象的鍵值對(duì)

利用對(duì)象的 key 不能重復(fù)的特性來去重； 之前看到有人使用對(duì)象的鍵值對(duì)去重的時(shí)候，直接將數(shù)組的每個(gè)值設(shè)置為對(duì)象的 key，value 都為1，每出現(xiàn)一個(gè)相同的值時(shí)就 value++，這樣既可以去重，又可以知道對(duì)應(yīng)的值出現(xiàn)的次數(shù)，例如：

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} 復(fù)制代碼

咋一看好像很完美，可是仔細(xì)一想，會(huì)發(fā)現(xiàn)有以下幾點(diǎn)原因：

• 若數(shù)組的值中出現(xiàn)了隱式類型轉(zhuǎn)換成字符串后相等的值，則無法區(qū)分，例如 '1' 和 1；
• 若數(shù)組中的值有對(duì)象，寫成 key 之后都是 [object Object]，無法區(qū)分；

解決方案：

若元素值的類型為 object，則通過 JSON.stringify 方法進(jìn)行轉(zhuǎn)換；

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; };// 實(shí)測(cè)耗時(shí)：142 ms 復(fù)制代碼

6、Set

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

/*** 實(shí)現(xiàn)方式一* 將數(shù)組轉(zhuǎn)換成 Set 對(duì)象* 通過 Array.from 方法將 Set 對(duì)象轉(zhuǎn)換為數(shù)組*/ 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); };// 實(shí)測(cè)耗時(shí)：45 ms/*** 實(shí)現(xiàn)方式二* 將數(shù)組轉(zhuǎn)換成 Set 對(duì)象* 通過 Array.from 方法將 Set 對(duì)象轉(zhuǎn)換為數(shù)組*/ Array.prototype.unique = function() {if(!Array.isArray(this)) throw new Error('Type Error: The target should be an Array!');return [...new Set(this)]; };// 實(shí)測(cè)耗時(shí)：65 ms 復(fù)制代碼

由以上耗時(shí)結(jié)果可以看出：

• filter, forEach 等方法都會(huì)對(duì)全數(shù)組進(jìn)行遍歷；
• indexOf, for+break, includes 等方法會(huì)對(duì)數(shù)組遍歷，在滿足條件的地方跳出遍歷

轉(zhuǎn)載于:https://juejin.im/post/5b2612e36fb9a00e50312e2d

總結(jié)

以上是生活随笔為你收集整理的数组去重的各种方式对比的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。