偶然和同事談到面試的Javascript問(wèn)題凳忙，其中基本上都會(huì)有一道問(wèn)題就是數(shù)組去重交排，隨著對(duì)于語(yǔ)言深入的學(xué)習(xí)乙帮，這道基礎(chǔ)問(wèn)題也有了更多的解法只壳。
理解問(wèn)題
該問(wèn)題要注意
- 兩個(gè)元素通過(guò)
===比較俏拱，返回true則視為相同元素，需要去重吕世，在此基礎(chǔ)下彰触，1和'1'是不同元素，1和new Number(1)是不同元素命辖，{}和{}是不同元素（引用不同）
基本解法
方法一：遍歷數(shù)組况毅，若存在于數(shù)組，則說(shuō)明是重復(fù)元素尔艇，將沒(méi)有的元素放入新數(shù)組
function unique(arr) {
var newArr = [];
for (var i = 0, len = arr.length; i < len; i ++) {
var item = arr[i];
for (var k = 0, kLen = newArr.length; k < kLen; k ++) {
if (newArr[k] === item) break;
}
if (k === kLen) newArr.push(item);
}
return newArr;
}
此方法復(fù)雜度為O(n^2)尔许，邏輯非常簡(jiǎn)單，大概的思路也如此终娃。
進(jìn)階一下味廊，使用indexOf方法簡(jiǎn)化
具體可以看看Javascript中的Array.prototype.indexOf()方法：
function unique(arr) {
var newArr = [];
for (var i = 0, len = arr.length; i < len; i ++) {
var item = arr[i];
(newArr.indexOf(item) === -1) && newArr.push(item);
}
return newArr;
}
其中(newArr.indexOf(item) === -1) && newArr.push(item)這種寫(xiě)法不太常見(jiàn)，這里也做個(gè)記錄
&& operator
Logical And
Usage: expr1 && expr2
Description:
Returns expr1 if it can be converted to false; otherwise, returns expr2.
Thus, when used with Boolean values, && returns true if both operands are true; otherwise, returns false.
--- MDN
即:
if (newArr.indexOf(item) === -1) newArr.push(item)
加入filter()方法
具體方法查閱Array.prototype.filter()
function unique(arr) {
var newArr = arr.filter(function(item, index, array){
return array.indexOf(item) === index;
})
return newArr;
}
// ES6寫(xiě)法
const unique = (arr) => arr.filter((item, index, arr) => array.indexOf(item) === index)
簡(jiǎn)潔的多棠耕，當(dāng)然這種寫(xiě)法考驗(yàn)jser對(duì)于數(shù)組相關(guān)方法的熟悉程度余佛。
進(jìn)階解法
當(dāng)考慮到算法復(fù)雜度的層面時(shí)，以上解法就顯得有些平庸了窍荧，這里我們考慮幾種進(jìn)階的方案辉巡。
擁抱ES6，使用Set和Array.from
Set對(duì)象見(jiàn)這里
Array.from()方法見(jiàn)這里
可以看到蕊退，Set是ES6中內(nèi)置的一個(gè)對(duì)象郊楣，是一些值的集合，可以遍歷循環(huán)其中元素的插入順序瓤荔，在Set中的值可能只出現(xiàn)一次净蚤，在集合中是獨(dú)一無(wú)二的。
而Array.from()則是ES6新增的數(shù)組方法输硝，他允許你基于array-like objects(objects with a length property and indexed elements)或者iterable obejcts(objects where you can get its elements such as Map and Set去創(chuàng)建一個(gè)數(shù)組今瀑。
基于以上兩個(gè)方法，我們可以這樣寫(xiě)：
function unique(arr) {
return Array.from(new Set(arr)); // return an array created by Set
}
以上方法針對(duì)的都是原始變量点把，當(dāng)元素為Object類(lèi)型時(shí)要作何處理呢
console.log(1 === 1) // true
console.log('1' === '1') // true
console.log({a: 1} === {a: 1}) //false
可以看出橘荠，{a: 1} === {a: 1}為false，這是因?yàn)閷?duì)象存儲(chǔ)的是引用愉粤，而原始變量存儲(chǔ)的則是值
因此我們需要換一個(gè)思路去實(shí)現(xiàn)砾医。
使用HashTable(哈希表)
HashTable在Javascript中是一個(gè)簡(jiǎn)單的Object，他的Key永遠(yuǎn)是String類(lèi)型衣厘，因此我們不能區(qū)分字符串和數(shù)字表示的相同的值如蚜，如1和'1'
var hashTable = {};
hashTable[1] = true;
hashTable['1'] = true;
console.log(hashTable);
// {'1': true}
那么如果要區(qū)分開(kāi)來(lái)，我們需要將Key變?yōu)槲ㄒ坏挠氨褂?code>JSON.stringify:
var hashTable = {};
hashTable[JSON.stringify(1)] = true;
hashTable[JSON.stringify('1')] = true;
console.log(hashTable); // {'1': true, '"1"': true}
綜上错邦，我們實(shí)現(xiàn)對(duì)于任何類(lèi)型元素進(jìn)行去重的方法：
function unique(arr) {
var hashTable = {};
return arr.filter(function(item) {
var key = JSON.stringify(item);
var match = Boolean(hashTable[key]);
return (match ? false: hashTable[key] = true);
})
}
閱讀材料：
Array.prototype.indexOf()
Array.prototype.filter()
Set
Array.from()
JSON.stringify()
Arrow functions
