陣列去重看起來簡單,但寫法差很多。這篇收錄兩種以 Array.prototype.del 為名的實作,剛好對應兩種不同的思路。
先把整個陣列倒進一個物件裡計數,凡是出現超過一次的,再把它的索引收集起來一次刪掉:
Array.prototype.del = function(){
var b = {}, c, i = 0, l = this.length, j;
for(; i < l; i++){
c = this.shift();
c in b ? b[c]++ : b[c] = 0;
}
for(j in b){
if(b[j] > 0) this.push(+j || j);
}
return this;
};
var a = [1, 2, 2, 3, 3, 3, 'a', 'b', 'b'];
alert(a.del());
這裡有兩個值得多看兩眼的細節:
shift() 直到取完,等於順便清空了 this,之後再 push 回來,就不需要另外處理「要不要保留原陣列」的問題。+j || j 的雙重轉型:物件的鍵一律是字串,所以 b 的屬性名都是 "1"、"2" 這種。前面加 + 可以轉回數字,但遇到 'a' 會得到 NaN(falsy),此時 || j 就退回原本的字串。一個運算式同時處理了數字與字串兩種情況,寫得相當聰明。另一種思路更精簡:邊走訪邊把值當鍵塞進空物件,沒見過就留下、見過就跳過,最後用陣列長度一次截斷:
Array.prototype.del = function(){
return (function (i, n, j, u, o){
for (; i < j; i++) {
o = this[i];
o in u ? 0 : (u[this[n++] = o] = 1)
}
this.length = n;
return this
}).call(this, 0, 0, this.length, {})
}
var a = [1, 2, 2, 3, 3, 3, 'a', 'b', 'b'];
alert(a.del());
這段程式碼密度很高,值得逐字拆解:
call(this, ...) 把原本的陣列傳進來當 this,同時用參數預告了 i、n、j、u、o 五個區域變數——這是為了不污染外部作用域。n 是寫入游標:它與 i 不同,只有「第一次見到」時才遞增。因為 n 恆小於等於 i,寫入永遠落後於讀取,不會覆蓋到還沒讀的資料。u[this[n++] = o] = 1:這一句子做了兩件事——把值寫回陣列的 n 位置並讓 n 前進,同時在雜湊表 u 裡標記「看過了」。運算式回傳的值剛好是索引,可以當運算結果繼續用。this.length = n:既然去重後只寫了 n 個元素,直接把長度截到 n 就完成了,不必刪除任何節點。第一種直觀好讀,適合維護中的專案;第二種只遍歷一次、沒有 shift 的搬移成本,效率更好,但可讀性代價明顯。若真要追求速度,用 indexOf 搭配 filter 也是常見選擇:
arr.filter(function(item, pos){
return arr.indexOf(item) === pos;
});
而 ES6 之後最乾脆的答案是 [...new Set(arr)]——一行搞定,語意清楚,效能也不差。上面這些手工實作的價值,在於它們示範了「用雜湊表把時間複雜度從 O(n²) 降到 O(n)」這個經典手法,而這正是 JavaScript 裡最常用的效能技巧之一。