要把多個陣列併成一個、只留下不重複的值,最直覺的做法是兩層迴圈比對,但那是 O(n²)。用「拼接 + 雜湊表」可以降到接近 O(n),程式碼還更短。
function uniqueMerge() {
var a = ["a", "b", "c"],
b = ["b", "c", "d"],
c = ["c", "d", "e"];
var _a = a.concat(b).concat(c), // 先全部接起來
_hash = {}, // 當成「看過了」的紀錄簿
_new = []; // 存放不重複的結果
for (var i = _a.length; i--;) {
if (!_hash[_a[i]]) {
_hash[_a[i]] = 1;
_new.push(_a[i]);
}
}
return _new; // ["e","d","c","b","a"](順序反轉,見下方說明)
}
第一步,concat 拼接。a.concat(b).concat(c) 產生一個包含全部元素的新陣列,且不修改原本三個陣列。
第二步,用物件當雜湊表。遍歷拼接後的陣列,把每個值當成物件的 key 寫進去。若這個 key 從沒出現過(!_hash[值] 為真),就同時做兩件事:在雜湊表上標記,並把它推進結果陣列。若已出現過就跳過。物件的屬性查找平均是常數時間,因此整體只要跑一輪。
迴圈方向。原寫法 for (var i = _a.length; i--;) 是倒著跑的,結果陣列的順序會反過來。若在意順序,改成 for (var i = 0; i < _a.length; i++) 即可。
用 Object.create(null) 更安全。普通物件的原型鏈上有 toString、valueOf、constructor 等屬性。若陣列裡剛好有字串 "toString",_hash["toString"] 會取到函式(truthy),導致這個值被誤判為重複而丟失。
// ES6 Set:一行解決,且天然支援物件與非字串值
var result = [...new Set([].concat(a, b, c))];
// 若要保留原順序,Set 本身就會照插入順序排列
var result2 = Array.from(new Set(a.concat(b, c)));
另外,ES5 的 filter 也能做到,且語意更清楚:
var seen = {};
var result3 = _a.filter(function (v) {
return seen.hasOwnProperty(v) ? false : (seen[v] = true);
});
選擇建議:新專案直接用 Set,程式最短也最不容易出錯;需要處理大量非字串資料(物件、數字)時尤其如此,因為物件當 key 會被轉成 "[object Object]",全部混在一起。