Array 類型並沒有內建的去重方法,要消除重複元素得自己動手。本文從最直觀的思路出發,逐步優化到 O(n) 的方案,並分析每一步的效率變化。
思路是新建一個結果數組,遍歷原數組,只在結果數組中不存在該元素時才追加進去。
var aa = [1, 3, 5, 4, 3, 3, 1, 4];
function unique(arr) {
var result = [];
for (var i = 0; i < arr.length; i++) {
if (result.indexOf(arr[i]) === -1) {
result.push(arr[i]);
}
}
console.log(result); // [1, 3, 5, 4]
}
unique(aa);
代碼最簡短,但要意識到 indexOf 本身是線性查找。外層循環 n 次,內層查找平均 n/2 次,整體時間複雜度是 O(n²)。數據量小沒問題,上千條以上就會明顯變慢。
不用 indexOf,改成顯式的嵌套循環加一個標記變量:
function unique(arr) {
var result = [], isRepeated;
for (var i = 0, len = arr.length; i < len; i++) {
isRepeated = false;
for (var j = 0, len2 = result.length; j < len2; j++) {
if (arr[i] === result[j]) {
isRepeated = true;
break;
}
}
if (!isRepeated) result.push(arr[i]);
}
return result;
}
本質與方法一相同:把元素逐个搬到新數組,搬運過程中檢查是否重複。從嵌套結構就能看出效率依然很低,仍然是 O(n²)。
既然瓶頸在於「查找是否已存在」,那就換一個查找是 O(1) 的結構。JavaScript 對象天然就是一個哈希表,用它記錄已有元素即可:
function unique(arr) {
var result = [], hash = {};
for (var i = 0, elem; (elem = arr[i]) != null; i++) {
if (!hash[elem]) {
result.push(elem);
hash[elem] = true;
}
}
return result;
}
時間複雜度降到 O(n),代碼量還減少了。這是最值得記住的手寫方案。
不過它有兩個需要留意的細節。一是循環終止條件,(elem = arr[i]) != null 用的是寬鬆比較,遇到數組中含有 null 或 undefined 的元素會提前結束,改成 i < arr.length 更穩妥。二是類型問題,對象的鍵會被強制轉成字符串,所以數字 1 和字符串 '1' 會被當成同一個鍵,hash[1] 與 hash['1'] 完全等價。需要嚴格區分類型時,可以給元素加上類型前綴,比如 typeof elem + elem 作為鍵。
如果環境允許,直接一行搞定,而且 Set 使用 SameValueZero 演算法比較,能正確處理 NaN 並區分數字與字符串:
var arr = [1, 3, 5, 4, 3, 3, 1, 4]; var result = [...new Set(arr)]; // [1, 3, 5, 4] // 或者 var result2 = Array.from(new Set(arr));
需要按對象的某個字段去重時,可以用 filter 配合 indexOf,或者基於 Map 實現:
var list = [
{ id: 1, name: 'a' },
{ id: 2, name: 'b' },
{ id: 1, name: 'c' }
];
// 按 id 去重,保留首次出現的一項
var seen = new Set();
var result = list.filter(function (item) {
if (seen.has(item.id)) return false;
seen.add(item.id);
return true;
});
三者對比很清晰:可讀性上 Set 最優、哈希表次之、indexOf 在邏輯上最直觀;性能上 Set 與哈希表都是 O(n),indexOf 是 O(n²)。所以:現代環境直接用 Set;需要兼容老瀏覽器時用哈希表方案;只有在數據量確定很小、追求代碼一眼看懂時,indexOf 才是合理選擇。
最後提醒一點,去重前先想清楚「相同」的定義。是值相等、類型也相等(Set 的行為),還是按某個業務主鍵相等?這個判斷比選哪種實現更影響最終結果的正確性。