陣列去重是面試與實務中都常出現的需求。本文先限定在「同型別資料」的單純情境,整理四種常見寫法,再從效能角度做個比較——畢竟思路清楚之外,能不能跑得夠快才是工程上的重點。
// 做法一:借助 indexOf 檢查是否已存在
Array.prototype.unique1 = function () {
var n = [];
for (var i = 0; i < this.length; i++) {
if (n.indexOf(this[i]) == -1) n.push(this[i]);
}
return n;
};
// 做法二:用 object 當雜湊表
Array.prototype.unique2 = function () {
var n = {}, r = [];
for (var i = 0; i < this.length; i++) {
if (!n[this[i]]) {
n[this[i]] = true;
r.push(this[i]);
}
}
return r;
};
// 做法三:比較第一次出現的位置
Array.prototype.unique3 = function () {
var n = [this[0]];
for (var i = 1; i < this.length; i++) {
if (this.indexOf(this[i]) == i) n.push(this[i]);
}
return n;
};
// 做法四:先排序,再比對相鄰元素
Array.prototype.unique4 = function () {
this.sort();
var re = [this[0]];
for (var i = 1; i < this.length; i++) {
if (this[i] !== re[re.length - 1]) re.push(this[i]);
}
return re;
};
var arr = [1, 2, 2, 2, 3, 3, 4, 5];
console.log(arr.unique1()); // [1, 2, 3, 4, 5]
console.log(arr.unique2()); // [1, 2, 3, 4, 5]
console.log(arr.unique3()); // [1, 2, 3, 4, 5]
console.log(arr.unique4()); // [1, 2, 3, 4, 5]
做法一與做法三都依賴陣列的 indexOf。這個方法的實作方式是從頭開始逐一比對直到找到目標,因此每插入一個元素,整體就多一次線性掃描,資料量大時會明顯變慢。
做法二改用雜湊表:把出現過的值以下標形式存進 object,後續只需一次屬性查找即可判定。屬性存取的時間複雜度遠優於線性搜尋,因此在這四種寫法裡效能最好。
做法四的思路是先排序,再比較相鄰兩項是否相同。排序用的是 JS 原生的 sort(引擎內部一般為快速排序)。實測顯示,它的平均執行時間約為做法二的三倍,但仍明顯快過做法一與做法三。
function unique(arr){...} 這類獨立函式更安全。[...new Set(arr)];物件陣列則可用 filter 搭配 findIndex 或 Map 來處理。理解這四種做法的取捨,重點不在背起來,而在建立「資料結構選擇會直接影響效能」這條直覺。