陣列去重是面試與實務都常見的小題目。用雙層迴圈比對雖然直觀,時間複雜度卻是 O(n²)。本文這版利用物件的屬性鍵唯一性,把成本壓到接近 O(n)。
把每個元素當成物件的鍵寫進暫存物件,重複的值會自然被覆蓋掉。跑完一輪後,再用 for...in 把鍵倒回陣列。因為屬性名只能是字串,這個做法對數字與字串陣列特別合適。
function unique(data) {
data = data || [];
var a = {};
for (var i = 0; i < data.length; i++) {
var v = data[i];
if (typeof(a[v]) == 'undefined') {
a[v] = 1;
}
};
data.length = 0; // 清空原陣列,保留同一個參考
for (var i in a) {
data[data.length] = i;
}
return data;
}
function test() {
var arr = [9, 1, 3, 8, 7, 7, 6, 6, 5, 7, 8, 8, 7, 4, 3, 1];
var arr1 = unique(arr);
alert(arr1.join(","));
}
test();
第一,data.length = 0 是清空而非重新指派的關鍵,這樣外部持有的參考仍指向同一個陣列。第二,for...in 取出的鍵都是字串,所以原本如果是數字,去重後會變成字串,必要時得用 parseFloat 轉回。第三,這個寫法不保證原本的元素順序。
若執行環境允許 ES6,直接用 Array.from(new Set(arr)) 或 [...new Set(arr)] 就能一行搞定,語意也更清楚。