陣列去重是前端面試的高頻題,也是實務上真的會遇到的需求。本文先給一個自己寫的直觀版本,再對照幾種常見寫法,順便談談各自的陷阱。
Array.prototype.unique = function () {
var oldArr = this,
newArr = [oldArr[0]],
len = oldArr.length,
i = 1;
if (!len) return this;
for (; i < len; i++) {
newArr.indexOf(oldArr[i]) < 0 ? newArr.push(oldArr[i]) : '';
}
return newArr;
};
var arr = ['a', 'a', 'b', 'a', 'c', 'd'];
console.log(arr.unique()); // ["a", "b", "c", "d"]
邏輯直白:預留第一個元素,後續每個元素先問 indexOf「你在新陣列裡嗎?」,不在才推進去。回傳新陣列,不動到原陣列。
自己寫一遍的好處是邏輯在腦中清楚,之後要擴充很容易——改成針對物件屬性去重、或同時處理多個陣列,都是順著這條思路往下長。
但這裡有個問題:直接掛在 Array.prototype 上會污染全域,任何 for...in 遍歷陣列的程式碼都可能因此出錯。實務上請寫成獨立函式。
function oSort(arr) {
var result = {};
var newArr = [];
for (var i = 0; i < arr.length; i++) {
if (!result[arr[i]]) {
newArr.push(arr[i]);
result[arr[i]] = 1;
}
}
return newArr;
}
用一個暫存物件記錄「看過哪些值」,查詢是 O(1),整體降到 O(n)。這是最經典的去重手法。
var student = ['qiang', 'ming', 'tao', 'li', 'liang', 'you', 'qiang', 'tao'];
function unique(arr) {
var tmp = [];
for (var i in arr) {
// 該元素在 tmp 中不存在才追加
if (tmp.indexOf(arr[i]) == -1) {
tmp.push(arr[i]);
}
}
return tmp;
}
概念與版本一相同,只是換成 for...in。要提醒的是,for...in 會遍歷繼承來的可列舉屬性,處理陣列時用傳統 for 或 forEach 更安全。
function unique(arr) {
var tmp = [];
for (var m in arr) {
tmp[arr[m]] = 1; // 值當鍵,重複的自動覆蓋
}
var tmparr = [];
for (var n in tmp) {
tmparr.push(n); // 再把鍵倒回來當值
}
return tmparr;
}
想法相當聰明:利用物件鍵的唯一性,重複值在賦值時自然被合併,最後把鍵名倒回陣列。缺點是所有值都被轉成字串,1 與 "1" 會被視為同一個。
/**
* 去除陣列重複元素
*/
function uniqueArray(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;
}
用 data.length = 0 清空陣列是個值得記的技巧,比重新指派人參更快也更乾淨。
上面五種寫法思路相近,效能差異主要在「查詢是否為 O(1)」:版本二與版本五用物件做雜湊,明顯快於版本一、三、四的線性搜尋。
但雜湊法有個共同的弱點——型別會被字串化,而且像 __proto__ 這種鍵名會造成物件原型污染。若要處理數字、物件或混合型別,用 Set 才是正確答案:
function unique(arr) {
return [...new Set(arr)];
}
// 依物件屬性去重
function uniqueBy(arr, key) {
var seen = new Set();
return arr.filter(function (item) {
if (seen.has(item[key])) return false;
seen.add(item[key]);
return true;
});
}
Set 的值比較使用 SameValueZero 演算法,能正確區分 1 與 "1",也不會有原型污染的顧慮。面試時寫出版本二展現思路,再補一句「實務上我會用 Set」,通常是比較完整的回答。