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

1. 雙重循環(huán)

這種方法就很直接，很好理解。那就是創(chuàng)建一個(gè)新的空數(shù)組，每次我們會(huì)從原數(shù)組中取出一個(gè)元素，拿它和新數(shù)組的元素進(jìn)行一一比較。如果在新數(shù)組沒(méi)發(fā)現(xiàn)和取出元素相等的元素，就將其放入這個(gè)新數(shù)組中；如果發(fā)現(xiàn)有和取出元素相等的元素，不放入新數(shù)組中。當(dāng)原數(shù)組中的數(shù)組全都取出來(lái)時(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 表示沒(méi)有執(zhí)行 break。
    }
    return res;
}

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

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

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

從后往前遍歷數(shù)組，檢測(cè)元素第一次出現(xiàn)的位置是否為當(dāng)前元素的位置。如果不是，說(shuō)明有重復(fù)，移除當(dāng)前元素；如果沒(méi)有，就不移除。

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

這種寫(xiě)法不需要?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ù)雜度的。說(shuō)個(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)就不寫(xiě)了。

3. 排序后去重

排序算法有很多種，我們就用 js 自帶的排序算法吧。順帶一說(shuō)，v8引擎 的 sort() 方法在數(shù)組長(zhǎng)度小于等于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;
}

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

4. 使用散列表

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

下面的實(shí)現(xiàn)使用的是普通對(duì)象作為散列表，有很大的局限性，無(wú)法對(duì) js對(duì)象 進(jìn)行去重（對(duì)象都會(huì)轉(zhuǎn)為類似 [object Object] 的字符串）。另外，對(duì)于js對(duì)象來(lái)說(shuō)，a['1'] 和 a[1] 是相等的，因?yàn)?會(huì)轉(zhuǎn)換為'1'，這樣就無(wú)法分辨出 1 和 '1'，從而錯(cuò)誤地在去重過(guò)程中丟棄其中的一個(gè)元素，所以我做了簡(jiǎn)單地改良，鍵名使用的不是 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)。

如果考慮對(duì)象也能去重，可以考慮使用 ES6 的 Map。

5. ES6 的 Set

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

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

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

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

考慮 NaN 的去重

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

簡(jiǎn)單來(lái)說(shuō)就是，判斷 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)去重

簡(jiǎn)單說(shuō)下 lodash 的 uniq 方法的源碼實(shí)現(xiàn)。

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

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

總結(jié)

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

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

參考

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