JavaScript數(shù)組去重的6種實(shí)現(xiàn)方式(從 O(n2) 到 O(n))
更新時(shí)間：2026年05月26日 09:37:15 作者：Darling嚕啦啦
數(shù)組去重是前端面試中的高頻題目,本文通過(guò) 6 種不同的實(shí)現(xiàn)方式,帶你從暴力雙重循環(huán)一路進(jìn)化到 ES6 的 Set 一行代碼,同時(shí)深入理解時(shí)間復(fù)雜度與空間復(fù)雜度的權(quán)衡,需要的朋友可以參考下
前言
今天在課程中，老師帶我們用 6 種不同的方式 解決了同一道題——數(shù)組去重。從最基礎(chǔ)的雙重循環(huán)，到利用數(shù)組 API，再到 ES6 的 Set，每種方法都有其獨(dú)特的思路和適用場(chǎng)景。
更重要的是，通過(guò)這道題，我真正理解了時(shí)間復(fù)雜度和空間復(fù)雜度的概念，以及"空間換時(shí)間"的算法思想。
一、編碼規(guī)范：寫(xiě)好函數(shù)的第一步
在開(kāi)始之前，先聊聊代碼規(guī)范。老師在課上反復(fù)強(qiáng)調(diào)：
1.1 注釋是代碼的一部分
/**
* @func 數(shù)組去重
* @param {Array} arr 數(shù)組
* @return {Array} 去重后的數(shù)組
* @author hzs
* @date 2026-05-25
*/
function unique(arr) {
// ...
}
代碼的開(kāi)發(fā)者和使用者可能不是同一個(gè)人，你可能忘記當(dāng)時(shí)為什么這么寫(xiě)。注釋會(huì)提高代碼的可讀性，是代碼的一部分。
1.2 函數(shù)設(shè)計(jì)三原則
| 原則 | 說(shuō)明 |
|---|---|
| 一個(gè)函數(shù)一個(gè)功能 | 單一職責(zé)，便于維護(hù)和測(cè)試 |
| 封裝復(fù)雜功能 | 調(diào)用者不需要了解內(nèi)部實(shí)現(xiàn) |
| 健壯性——校驗(yàn)參數(shù) | 對(duì)輸入進(jìn)行類(lèi)型檢查，避免異常 |
1.3 參數(shù)校驗(yàn)?zāi)０?/h3>
function unique(arr) {
// Array.isArray() 是數(shù)組的靜態(tài)方法，無(wú)需實(shí)例化即可調(diào)用
if (!Array.isArray(arr)) {
console.log('type error');
return [];
}
// ...具體邏輯
}
以下 6 種實(shí)現(xiàn)都會(huì)包含這個(gè)參數(shù)校驗(yàn)，后續(xù)代碼中不再重復(fù)說(shuō)明。
function unique(arr) {
// Array.isArray() 是數(shù)組的靜態(tài)方法，無(wú)需實(shí)例化即可調(diào)用
if (!Array.isArray(arr)) {
console.log('type error');
return [];
}
// ...具體邏輯
}
以下 6 種實(shí)現(xiàn)都會(huì)包含這個(gè)參數(shù)校驗(yàn)，后續(xù)代碼中不再重復(fù)說(shuō)明。
二、方法一：雙重循環(huán)（暴力法）
思路
維護(hù)一個(gè)結(jié)果數(shù)組 res，遍歷原數(shù)組，對(duì)每個(gè)元素檢查是否已存在于 res 中。
function unique(arr) {
if (!Array.isArray(arr)) {
console.log('type error');
return [];
}
let res = [arr[0]];
for (let i = 1; i < arr.length; i++) {
let flag = true; // 標(biāo)記是否重復(fù)
for (let j = 0; j < res.length; j++) {
// === 恒等：值相等且類(lèi)型相等
// 1 === '1' → false（弱類(lèi)型語(yǔ)言中的嚴(yán)格比較）
if (arr[i] === res[j]) {
flag = false;
break;
}
}
if (flag) {
res.push(arr[i]);
}
}
return res;
}
console.log(unique([1, 2, 3, 4, 5, 5, 6]));
// [1, 2, 3, 4, 5, 6]
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n2)
├── 外層循環(huán) n 次
└── 內(nèi)層循環(huán)最多 n 次
總計(jì)：n × n = n2
空間復(fù)雜度：O(n)
└── 結(jié)果數(shù)組 res 最多存儲(chǔ) n 個(gè)元素
優(yōu)點(diǎn)：思路最直觀，適合初學(xué)者理解。缺點(diǎn)：性能差，數(shù)據(jù)量大時(shí)明顯卡頓。
三、方法二：indexOf 優(yōu)化
思路
利用 Array.prototype.indexOf() 方法替代內(nèi)層循環(huán)，判斷元素是否已存在于結(jié)果數(shù)組中。
function unique(arr) {
if (!Array.isArray(arr)) {
console.log('type error');
return [];
}
const res = [];
for (let i = 0; i < arr.length; i++) {
// indexOf 返回元素第一次出現(xiàn)的索引
// 如果返回 -1，說(shuō)明 res 中不存在該元素
if (res.indexOf(arr[i]) === -1) {
res.push(arr[i]);
}
}
return res;
}
關(guān)鍵 API
arr.indexOf(item) // 返回 item 在 arr 中第一次出現(xiàn)的索引 // 找不到返回 -1 [1, 2, 3, 2].indexOf(2) // 1 [1, 2, 3].indexOf(4) // -1
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n2)
├── 外層循環(huán) n 次
└── indexOf 內(nèi)部也是一次遍歷 O(n)
總計(jì)：仍然是 n2
空間復(fù)雜度：O(n)
本質(zhì)上和方法一相同，只是用 indexOf 替代了手寫(xiě)內(nèi)層循環(huán)，代碼更簡(jiǎn)潔，但時(shí)間復(fù)雜度沒(méi)有改善。
四、方法三：filter + indexOf
思路
利用 Array.prototype.filter() 方法，配合 indexOf 進(jìn)行過(guò)濾。
function unique(arr) {
if (!Array.isArray(arr)) {
console.log('type error');
return [];
}
return arr.filter(function(item, index) {
// 只保留第一次出現(xiàn)的元素
// indexOf 返回第一個(gè)索引，如果等于當(dāng)前 index，說(shuō)明是第一次出現(xiàn)
return index === arr.indexOf(item);
});
}
console.log(unique([1, 2, 3, 4, 5, 5, 6]));
// [1, 2, 3, 4, 5, 6]
關(guān)鍵 API
arr.filter(function(item, index) {
// 返回 true → 保留該元素
// 返回 false → 過(guò)濾掉該元素
return true | false;
});
工作原理
原數(shù)組：[1, 2, 3, 4, 5, 5, 6] 索引： 0 1 2 3 4 5 6 filter 遍歷過(guò)程： ┌──────┬───────┬────────────────┬────────┐ │ item │ index │ indexOf(item) │ 保留？ │ ├──────┼───────┼────────────────┼────────┤ │ 1 │ 0 │ 0 │ ? │ │ 2 │ 1 │ 1 │ ? │ │ 3 │ 2 │ 2 │ ? │ │ 4 │ 3 │ 3 │ ? │ │ 5 │ 4 │ 4 │ ? │ │ 5 │ 5 │ 4 │ ? │ ← 第二個(gè) 5 被過(guò)濾 │ 6 │ 6 │ 6 │ ? │ └──────┴───────┴────────────────┴────────┘
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n2)
├── filter 遍歷 n 次
└── 每次 indexOf 遍歷 O(n)
總計(jì)：仍然是 n2
空間復(fù)雜度：O(n)
函數(shù)式編程風(fēng)格，代碼最簡(jiǎn)潔優(yōu)雅，但性能上仍然是 O(n²)。
五、方法四：排序后相鄰比較
思路
先對(duì)數(shù)組排序，然后只需比較相鄰元素是否相同。
function unique(arr) {
if (!Array.isArray(arr)) {
console.log('type error');
return [];
}
// O(n2) → O(nlogn)
arr = arr.sort();
let res = [arr[0]];
for (let i = 1; i < arr.length; i++) {
// 相鄰元素不相等，保留
if (arr[i] !== arr[i - 1]) {
res.push(arr[i]);
}
}
return res;
}
為什么更快？
排序前：[3, 1, 4, 1, 5, 9, 2, 6, 5]
排序后：[1, 1, 2, 3, 4, 5, 5, 6, 9]
↑ ↑
相鄰比較即可，無(wú)需兩兩比較
復(fù)雜度分析
時(shí)間復(fù)雜度：O(nlogn)
├── sort() 排序：O(nlogn)
└── 遍歷比較：O(n)
總計(jì)：O(nlogn) + O(n) = O(nlogn) ← 顯著提升！
空間復(fù)雜度：O(n)
性能提升明顯，從 O(n²) 降到 O(nlogn)。但注意：sort() 默認(rèn)按字符串排序，對(duì)數(shù)字?jǐn)?shù)組需要傳入比較函數(shù) arr.sort((a, b) => a - b)。
六、方法五：對(duì)象字面量 / HashMap（空間換時(shí)間）
思路
利用 JavaScript 對(duì)象字面量作為 HashMap，以數(shù)組元素為 key，實(shí)現(xiàn) O(1) 的查找。
function unique(arr) {
if (!Array.isArray(arr)) {
console.log('type error');
return [];
}
let res = [],
obj = {}; // 對(duì)象字面量充當(dāng) HashMap
for (let i = 0; i < arr.length; i++) {
// obj[variable] — 變量作為 key（動(dòng)態(tài)屬性訪問(wèn)）
// obj.name — 常量作為 key（點(diǎn)號(hào)訪問(wèn)）
if (!obj[arr[i]]) {
res.push(arr[i]);
obj[arr[i]] = 1; // 標(biāo)記為已存在
} else {
obj[arr[i]]++; // 記錄出現(xiàn)次數(shù)
}
}
return res;
}
核心原理
對(duì)象字面量充當(dāng) HashMap
遍歷 [1, 2, 3, 2, 4, 3]
Step 1: obj = {}, res = [1] obj[1] = 1
Step 2: obj = {1:1}, res = [1,2] obj[2] = 1
Step 3: obj = {1:1,2:1}, res = [1,2,3] obj[3] = 1
Step 4: obj[2] 已存在！跳過(guò)
Step 5: obj = {1:1,2:1,3:1}, res = [1,2,3,4] obj[4] = 1
Step 6: obj[3] 已存在！跳過(guò)
結(jié)果：[1, 2, 3, 4]
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)
├── 只需遍歷一次數(shù)組
└── 對(duì)象屬性查找是 O(1)
總計(jì)：O(n) × O(1) = O(n) ← 最優(yōu)！
空間復(fù)雜度：O(n)
├── 結(jié)果數(shù)組 O(n)
└── HashMap 對(duì)象 O(n)
總計(jì)：O(n) ← 用空間換時(shí)間
經(jīng)典的空間換時(shí)間策略。JavaScript 早期沒(méi)有 HashMap，對(duì)象字面量就是最好的替代方案。注意：如果數(shù)組元素是對(duì)象，需要用 JSON.stringify() 轉(zhuǎn)換為字符串作為 key。
七、方法六：ES6 Set（終極方案）
思路
利用 ES6 新增的 Set 數(shù)據(jù)結(jié)構(gòu)——天生不重復(fù)的集合。
function unique(arr) {
if (!Array.isArray(arr)) {
console.log('type error');
return [];
}
return [...new Set(arr)]; // Set 轉(zhuǎn)換為數(shù)組
}
一行代碼搞定
const unique = arr => [...new Set(arr)];
Set 是什么？
Set 的特性 ├── 不重復(fù)的數(shù)據(jù)容器 ├── 內(nèi)部使用 HashMap 實(shí)現(xiàn) ├── 查找/插入的時(shí)間復(fù)雜度 O(1) └── ES6 新增的數(shù)據(jù)結(jié)構(gòu)
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)
├── new Set(arr)：遍歷數(shù)組構(gòu)建 Set，O(n)
└── ...展開(kāi)運(yùn)算符：遍歷 Set 轉(zhuǎn)數(shù)組，O(n)
總計(jì)：O(n)
空間復(fù)雜度：O(n)
└── Set 容器存儲(chǔ) n 個(gè)元素
生產(chǎn)環(huán)境推薦方案：代碼最簡(jiǎn)潔、性能最優(yōu)、語(yǔ)義最清晰。
八、六種方法全面對(duì)比
8.1 復(fù)雜度對(duì)比
| 方法 | 時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 核心思路 |
|---|---|---|---|
| ① 雙重循環(huán) | O(n²) | O(n) | 暴力枚舉 |
| ② indexOf | O(n²) | O(n) | API 替代內(nèi)層循環(huán) |
| ③ filter+indexOf | O(n²) | O(n) | 函數(shù)式風(fēng)格 |
| ④ 排序+相鄰比較 | O(nlogn) | O(n) | 先排序降低比較次數(shù) |
| ⑤ 對(duì)象字面量/HashMap | O(n) | O(n) | 空間換時(shí)間 |
| ⑥ ES6 Set | O(n) | O(n) | 利用 Set 天生去重 |
8.2 復(fù)雜度直觀感受
執(zhí)行時(shí)間對(duì)比（假設(shè) n = 10000） O(n2) ：100,000,000 次操作 ?? O(nlogn) ： 132,877 次操作 ?? O(n) ： 10,000 次操作 ?? 差距巨大！算法選擇直接影響程序性能
8.3 適用場(chǎng)景
| 場(chǎng)景 | 推薦方法 | 原因 |
|---|---|---|
| 生產(chǎn)環(huán)境 | ⑥ Set | 簡(jiǎn)潔、高效、現(xiàn)代 |
| 面試手寫(xiě) | ⑤ HashMap | 展示算法思維 |
| 學(xué)習(xí)理解 | ①②③④ | 理解基本原理 |
| 大數(shù)據(jù)量 | ④⑤⑥ | 避免 O(n²) |
| 兼容舊瀏覽器 | ④⑤ | 不依賴(lài) ES6 |
九、涉及的核心數(shù)組 API
速查表
| API | 類(lèi)型 | 作用 | 示例 |
|---|---|---|---|
Array.isArray() | 靜態(tài)方法 | 判斷是否是數(shù)組 | Array.isArray([1]) → true |
arr.indexOf(item) | 實(shí)例方法 | 返回首次出現(xiàn)的索引 | [1,2,3].indexOf(2) → 1 |
arr.filter(fn) | 實(shí)例方法 | 過(guò)濾數(shù)組，返回新數(shù)組 | arr.filter(x => x > 0) |
arr.sort() | 實(shí)例方法 | 排序（原地修改） | arr.sort((a,b) => a-b) |
十、知識(shí)圖譜
?? 數(shù)組去重知識(shí)圖譜
編碼規(guī)范
├── JSDoc 注釋規(guī)范
├── 一個(gè)函數(shù)一個(gè)功能
├── 參數(shù)校驗(yàn)（健壯性）
└── === 嚴(yán)格相等
六種實(shí)現(xiàn)方式
├── O(n2) 暴力法
│ ├── 雙重循環(huán)
│ ├── indexOf
│ └── filter + indexOf
│
├── O(nlogn) 排序法
│ └── sort + 相鄰比較
│
└── O(n) 哈希法
├── 對(duì)象字面量 / HashMap
└── ES6 Set
核心概念
├── 時(shí)間復(fù)雜度（執(zhí)行效率）
├── 空間復(fù)雜度（內(nèi)存占用）
├── 空間換時(shí)間（算法權(quán)衡）
└── HashMap 原理（O(1) 查找）
結(jié)語(yǔ)
一道簡(jiǎn)單的數(shù)組去重題，從 O(n²) 到 O(n)，從暴力循環(huán)到 Set 一行代碼，背后是算法思維的進(jìn)化。
面試中，面試官考的不僅是你能不能寫(xiě)出答案，更是你能否分析不同方案的時(shí)間復(fù)雜度和空間復(fù)雜度，能否根據(jù)實(shí)際場(chǎng)景選擇最優(yōu)方案。
記住這六個(gè)方法，理解背后的原理，你就能在面試中游刃有余。
以上就是JavaScript數(shù)組去重的6種實(shí)現(xiàn)方式(從 O(n²) 到 O(n))的詳細(xì)內(nèi)容，更多關(guān)于JavaScript數(shù)組去重實(shí)現(xiàn)方式的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
給網(wǎng)頁(yè)正文提供，小 中 大 三種字體的切換功能。用js代碼設(shè)置div style的fontSize屬性。2009-06-06
這篇文章主要介紹了JavaScript柯里化函數(shù)式編程，JS柯里化是前端面試中最常見(jiàn)的問(wèn)題之一，它可以讓你的代碼更簡(jiǎn)潔，工作更高效，感興趣想要詳細(xì)了解可以參考下文2023-05-05
在開(kāi)發(fā)的時(shí)候?yàn)槭裁醋筮叺臄?shù)據(jù)出來(lái)比右邊的慢呢？因?yàn)檫@里沒(méi)有進(jìn)行分頁(yè)，左邊的數(shù)據(jù)多，所以查詢(xún)相對(duì)較慢。怎么解決此問(wèn)題呢？下面小編給大家?guī)?lái)了JS鼠標(biāo)滾動(dòng)分頁(yè)效果示例，需要的的朋友參考下吧2017-07-07
javascript使用Promise對(duì)象實(shí)現(xiàn)異步編程
這篇文章主要介紹了javascript使用Promise對(duì)象實(shí)現(xiàn)異步編程的相關(guān)資料,需要的朋友可以參考下2016-03-03
JavaScript定時(shí)器實(shí)現(xiàn)的原理分析
JavaScript中的定時(shí)器大家基本在平時(shí)的開(kāi)發(fā)中都遇見(jiàn)過(guò)吧，但是又有多少人去深入的理解其中的原理呢？本文我們就來(lái)分析一下定時(shí)器的實(shí)現(xiàn)原理、定時(shí)器的妙用、定時(shí)器使用注意事項(xiàng)，有興趣的朋友可以看下2016-12-12
微信小程序局部刷新觸發(fā)整頁(yè)刷新效果的實(shí)現(xiàn)代碼
這篇文章主要介紹了微信小程序局部刷新觸發(fā)整頁(yè)刷新效果的實(shí)現(xiàn)代碼,非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2018-11-11
JavaScript 實(shí)現(xiàn)鼠標(biāo)拖動(dòng)元素實(shí)例代碼
這篇文章主要介紹了JavaScript 實(shí)現(xiàn)鼠標(biāo)拖動(dòng)元素實(shí)例代碼,需要的朋友可以參考下2014-02-02
微信小程序 多行文本顯示...+顯示更多按鈕和收起更多按鈕功能
這篇文章主要介紹了微信小程序多行文本顯示...+顯示更多按鈕和收起更多按鈕,代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-09-09
如何利用jszip庫(kù)實(shí)現(xiàn)文件壓縮與解壓功能
本章介紹了在使用jszip庫(kù)時(shí),開(kāi)發(fā)者如何檢測(cè)不同瀏覽器版本并實(shí)施兼容性解決方案,同時(shí)提供了相關(guān)的代碼示例和調(diào)試技巧,以便于讀者能夠更好地理解和運(yùn)用這些概念,感興趣的朋友跟隨小編一起看看吧2025-09-09
這篇文章主要介紹了JavaScript中var與let的區(qū)別，var是JavaScript剛出現(xiàn)時(shí)就存在的變量聲明關(guān)鍵字，而let作為ES6才出現(xiàn)的變量聲明關(guān)鍵字，無(wú)疑兩者之間存在著很大的區(qū)別，下面來(lái)看看兩者之間到底存在什么2021-12-12