數(shù)組去重 是常見的面試考點(diǎn)，所以我就試著深入學(xué)習(xí)一下黍聂。網(wǎng)上也有很多數(shù)組去重的文章，但我自己覺得分析地不夠深入身腻，其實(shí)其中很多的實(shí)現(xiàn)都是重復(fù)的产还，可以歸為一類，比如 雙重循環(huán)法 和 indexOf法 的本質(zhì)都是雙重循環(huán)嘀趟，故寫下此文脐区，做進(jìn)一步的總結(jié)，同時(shí)加深理解她按。

1. 雙重循環(huán)

這種方法就很直接牛隅，很好理解。那就是創(chuàng)建一個(gè)新的空數(shù)組酌泰，每次我們會(huì)從原數(shù)組中取出一個(gè)元素媒佣，拿它和新數(shù)組的元素進(jìn)行一一比較。如果在新數(shù)組沒發(fā)現(xiàn)和取出元素相等的元素陵刹，就將其放入這個(gè)新數(shù)組中默伍；如果發(fā)現(xiàn)有和取出元素相等的元素，不放入新數(shù)組中。當(dāng)原數(shù)組中的數(shù)組全都取出來時(shí)也糊，這個(gè)新數(shù)組就是去重后的所有數(shù)據(jù)了炼蹦。

這種數(shù)組去重的實(shí)現(xiàn)的時(shí)間復(fù)雜度是 O(n^2)。

const unique = arr => {
    let res = [];
    for (let i = 0, len = arr.length; i < len; i++) {
        let j = 0, len2 = res.length;
        for (; j < len2; j++) {
            if (arr[i] === res[j]) break;
        }
        if (j == len2) res.push(arr[i]);  // j == len2 表示沒有執(zhí)行 break显设。
    }
    return res;
}

當(dāng)然這里的第一個(gè)循環(huán)可以改為 forEach() 方法框弛，第二個(gè) for 循環(huán)可以改為使用 includes() 或者 indexOf() 方法，時(shí)間復(fù)雜度沒什么變化捕捂，不過代碼更簡潔瑟枫。

const unique = arr => {
    let res = [];
    arr.forEach(item => {
        if (!res.includes(item)) res.push(item); 
    })
    return res;
} 

2. 查找元素第一次出現(xiàn)的位置

從后往前遍歷數(shù)組，檢測元素第一次出現(xiàn)的位置是否為當(dāng)前元素的位置指攒。如果不是慷妙，說明有重復(fù)，移除當(dāng)前元素允悦；如果沒有膝擂，就不移除。

之所以從后往前遍歷隙弛，是因?yàn)槲覀円嵋圃兀ㄆ鋵?shí)就是 splice）架馋。當(dāng)然你也可以選擇從前往后遍歷，不過這樣的話全闷，如果遍歷時(shí)當(dāng)前元素被移除了叉寂，那么移除元素后的 arr[i] 對應(yīng)的元素其實(shí)是原來 arr[i+1]，因此此時(shí) i 不能自增总珠，且結(jié)束的條件要改為 i == len-1屏鳍，就很麻煩。

這種寫法不需要?jiǎng)?chuàng)建新的數(shù)組局服，空間復(fù)雜度為 O(1)钓瞭。

const unique = arr => {
    for (let i = arr.length - 1; i >= 0; i--) {
        for (let j = 0; j < i; j++) {
            if (arr[j] === arr[i]) arr.splice(i, 1);
        }
    }
    return arr;
}

這里的代碼實(shí)現(xiàn)是盡量減少時(shí)間復(fù)雜度的。說個(gè)題外話淫奔，其實(shí)上面這里還可以再優(yōu)化一下山涡，因?yàn)槲覀冞@里的元素搬移并不是一次性搬移到最終的位置上的。優(yōu)化思路是先標(biāo)記要所有要?jiǎng)h除的元素索引唆迁，然后從前往后遍歷數(shù)組佳鳖，每遇到第 m 個(gè)刪除索引，后面的元素就覆蓋掉它們往前第 m 位的數(shù)組元素媒惕，這里就不實(shí)現(xiàn)了系吩，也就隨便提一下。

如果改為配合使用 filter() 和 includes() 方法的話妒蔚，我們可以讓代碼可讀性更好一些（性能會(huì)稍微下降穿挨，因?yàn)?incluedes 會(huì)遍歷整個(gè)數(shù)組）月弛，具體實(shí)現(xiàn)就不寫了。

3. 排序后去重

排序算法有很多種科盛，我們就用 js 自帶的排序算法吧帽衙。順帶一說，v8引擎 的 sort() 方法在數(shù)組長度小于等于10的情況下贞绵，會(huì)使用插入排序厉萝，大于10的情況下會(huì)使用快速排序。

排（guai）好（guai）序（zhanhao）后榨崩，檢查前后兩個(gè)相鄰元素谴垫，如果當(dāng)前元素和前面的元素不相等，才將當(dāng)前元素放入新數(shù)組中母蛛。

const unique = arr => {
    if (arr.length < 2) return arr; 
    arr.sort();
    let r = [arr[0]];
    for (let i = 1, len = arr.length; i < len; i++) {
        if (a[i] !== a[i - 1]) r.push(a[i]);
    }
    return r;
}

這種去重局限性非常大翩剪。它不適用于對象，因?yàn)閷ο蟛贿m合進(jìn)行排序彩郊。sort() 的默認(rèn)排序順序是根據(jù)字符串Unicode碼點(diǎn)進(jìn)行排序前弯，貌似會(huì)把對象轉(zhuǎn)為字符串再進(jìn)行排序，一般的對象都會(huì)轉(zhuǎn)為 "[object Object]"秫逝，無法保證兩個(gè)引用同一個(gè)對象的變量能相鄰排列恕出。

4. 使用散列表

散列表，在 JavaScript 中是通過對象來實(shí)現(xiàn)的违帆。散列表的優(yōu)點(diǎn)是浙巫，一般情況下讀取數(shù)據(jù)的時(shí)間復(fù)雜度是 O(1)。但 js 的對象的鍵只能為字符串類型前方，不過可以考慮使用 ES6 新增的 Map 數(shù)據(jù)結(jié)構(gòu)，它允許使用任何類型的值作為鍵廉油。

下面的實(shí)現(xiàn)使用的是普通對象作為散列表惠险，有很大的局限性，無法對 js對象 進(jìn)行去重（對象都會(huì)轉(zhuǎn)為類似 [object Object] 的字符串）抒线。另外班巩，對于js對象來說，a['1'] 和 a[1] 是相等的嘶炭，因?yàn)?會(huì)轉(zhuǎn)換為'1'抱慌，這樣就無法分辨出 1 和 '1'，從而錯(cuò)誤地在去重過程中丟棄其中的一個(gè)元素眨猎，所以我做了簡單地改良抑进，鍵名使用的不是 arr[i] 而是 typeof(arr[i]) + arr[i]。

const unique = arr => {
    let r = [];
    let map = {};
    for (let i = 0, len = arr.length; i < len; i++) {
        const item = arr[i];
        if (!map[typeof(item) + item]) {
            r.push(arr[i]);
        }
        map[typeof(item) + item] = true; 
    }
    return r;
} 

這種實(shí)現(xiàn)方式睡陪，時(shí)間復(fù)雜度可以達(dá)到 O(n)寺渗。

如果考慮對象也能去重匿情，可以考慮使用 ES6 的 Map。

5. ES6 的 Set

ES6 提供了新的數(shù)據(jù)結(jié)構(gòu)信殊。Set 實(shí)例會(huì)認(rèn)為兩個(gè) NaN 是相等的（盡管 NaN !== NaN）炬称，并認(rèn)為兩個(gè)對象是不等的（當(dāng)然這里兩個(gè)對象的意思，表示的是兩個(gè)指向不同內(nèi)存空間的引用類型變量）涡拘。

并不太了解 Set 的源碼實(shí)現(xiàn)玲躯，就不分析性能了。

const unique = arr => {
    return Array.from(new Set(arr))
}

非常簡潔鳄乏，如果你的運(yùn)行環(huán)境支持 ES6跷车，或者可以編譯成 ES5，我很推薦使用這個(gè)去重方案汞窗。

考慮 NaN 的去重

如果要考慮 NaN 的去重姓赤，就需要稍微對代碼進(jìn)行一些修改。

簡單來說就是仲吏，判斷 item 是否為 NaN不铆，然后檢查返回的數(shù)組中是否已有 NaN。如果有裹唆，放入數(shù)組誓斥；否則不放入。

const unique = arr => {
    let res = [];
    let hasNaN = false;
    arr.forEach(item => {
        if(!hasNaN && Number.isNaN(item)) {
            res.push(item);
            hasNaN = true
        }else if (!res.includes(item)) {
            res.push(item); 
        }
    })
    return res;
} 

lodash 如何實(shí)現(xiàn)去重

簡單說下 lodash 的 uniq 方法的源碼實(shí)現(xiàn)许帐。

這個(gè)方法的行為和使用 Set 進(jìn)行去重的結(jié)果一致劳坑。

當(dāng)數(shù)組長度大于等于 200 時(shí)，會(huì)創(chuàng)建 Set 并將 Set 轉(zhuǎn)換為數(shù)組來進(jìn)行去重（Set 不存在情況的實(shí)現(xiàn)不做分析）成畦。當(dāng)數(shù)組長度小于 200 時(shí)距芬，會(huì)使用類似前面提到的 雙重循環(huán) 的去重方案，另外還會(huì)做 NaN 的去重循帐。

總結(jié)

一般來說框仔，在開發(fā)中，要進(jìn)行去重的數(shù)組并不是很大拄养，不必太考慮性能問題离斩。所以在工程中，為了不把簡單的問題復(fù)雜化中瘪匿，建議使用最簡潔的 ES6 的 Set 轉(zhuǎn)數(shù)組的方案來實(shí)現(xiàn)跛梗。當(dāng)然具體問題具體分析，要根據(jù)場景選擇真正合適的去重方案棋弥。

另外核偿，其實(shí) “相等” 有很多種定義，ES6 中就有四種相等算法顽染，這里就不多說了宪祥，有興趣的話可以看看這篇文章：JavaScript 中的相等性判斷聂薪。依舊是根據(jù)場景選擇合適的相等算法。

參考

• 掘金--7種方法實(shí)現(xiàn)數(shù)組去重
• JavaScript專題之?dāng)?shù)組去重
• lodash 的 uniq 方法實(shí)現(xiàn)
• JavaScript 中的相等性判斷