DIV CSS 佈局教程網

合併三個陣列並去除重複元素:concat 加雜湊表的經典解法
編輯:JavaScript綜合知識     

要把多個陣列併成一個、只留下不重複的值,最直覺的做法是兩層迴圈比對,但那是 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]",全部混在一起。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved