陣列去重是面試常見題,也是實務上偶爾會遇到的需求。坊間流傳的寫法很多,但它們的時間複雜度差異不小。以下四種由慢到快排列,並說明各自的適用時機。
Array.prototype.unique1 = function () {
const result = [];
for (let i = 0; i < this.length; i++) {
if (result.indexOf(this[i]) === -1) result.push(this[i]);
}
return result;
};
思路最直覺,但 indexOf 本身是線性搜尋,包在迴圈裡就變成平方級。資料量一大就會明顯變慢。
Array.prototype.unique2 = function () {
const seen = {}, result = [];
for (let i = 0; i < this.length; i++) {
if (!seen[this[i]]) {
seen[this[i]] = true;
result.push(this[i]);
}
}
return result;
};
把已經出現過的值當成物件的 key 記錄下來。屬性查找是常數時間,因此整體是線性的,這四種裡最快。
但要注意:物件 key 一律是字串,所以數字 1 和字串 '1' 會被視為同一項。另外 seen['toString'] 這類繼承而來的屬性會誤判,穩妥寫法是改用 Set(見下)或 Object.create(null)。
Array.prototype.unique3 = function () {
const result = [this[0]];
for (let i = 1; i < this.length; i++) {
if (this.indexOf(this[i]) === i) result.push(this[i]);
}
return result;
};
原理是「若某項第一次出現的位置正好是當前索引,它就是首次出現」。看起來比寫法一聰明,但 indexOf 仍舊是線性搜尋,複雜度一樣是平方級。
Array.prototype.unique4 = function () {
const sorted = this.slice().sort();
const result = [sorted[0]];
for (let i = 1; i < sorted.length; i++) {
if (sorted[i] !== result[result.length - 1]) result.push(sorted[i]);
}
return result;
};
排序後重複項必然相鄰,因此只需比對前一個。排序本身是 n log n,實測通常比寫法一、三快,但仍是寫法二的三倍左右。
注意這裡加了 slice():直接 this.sort() 會改動原陣列,這是原型擴充最容易被詬病的副作用。
ES2015 之後,這個問題已經不需要自己寫了:
const arr = [1, 2, 2, 2, 3, 3, 4, 5]; [...new Set(arr)]; // [1, 2, 3, 4, 5] Array.from(new Set(arr)); // 同上,另一種轉回陣列的寫法
Set 天生不允許重複,內部用雜湊實作,時間複雜度 O(n),而且用 SameValueZero 演算法比較,所以 NaN 能被正確去重(indexOf 做不到),物件與陣列也能各自獨立保留。
要自訂比較邏輯(例如依 id 去重物件)時,可以搭配 filter 或直接操作 Map:
const byId = arr.filter((item, i, list) => list.findIndex(x => x.id === item.id) === i );
原始寫法把 unique 掛在 Array.prototype 上,看起來呼叫很順,但實務上不建議:一旦與其他函式庫或 polyfill 撞名,就會出現難以追蹤的衝突;而且 for...in 遍歷陣列時會把這個方法也列舉出來。改成獨立函式 unique(arr) 或用 Set,都是更安全的选择。
總結一句:新專案直接用 new Set();面試時能說出「indexOf 是平方級、雜湊是線性、排序是 n log n」這三種複雜度的差別,比背出任何一段程式碼都有說服力。