DIV CSS 佈局教程網

JavaScript 陣列去重的實作方式
編輯:關於JavaScript     

題目:寫一個函式去掉陣列中的重複值。傳入 [0, 8, 5, 4, 78, 8, 90, 4, 'a', 'b', 'a'],要求回傳 [0, 4, 5, 8, 78, 90, 'a', 'b']。

這題看起來簡單,但要在「不破壞原陣列」與「時間複雜度低」之間取得平衡,其實需要一點想法。

思路一:排序後依序刪除(不採用)

先把陣列排序,再逐一刪掉相鄰的相同元素。問題是排序會改變原陣列的順序,元素的「原有屬性」被破壞了,不符合題目要求,直接放棄。

思路二:逐一檢查再 push(O(n²))

建立新陣列 b,把 a 的元素一個個 push 進去,但 push 之前先檢查該元素是否已存在。這是最直覺也最笨的作法,時間複雜度 n²,資料量大時會很慢。

思路三:借重物件的屬性表(採用)

關鍵洞察是:JavaScript 物件的屬性查找接近 O(1),而屬性名不可能重複。於是可以用一個空物件當「已出現過的集合」:

var getNR = function (src) {
  src = src || [];
  var res = {};
  var curr = [];
  var i, j = 0, temp, name;
  for (i = 0; i < src.length; i++) {
    temp = src[i];
    if (res[temp]) {
      // 已存在,甚麼都不做
    } else {
      res[temp] = 1;
    }
  }
  for (name in res) {
    if (res.hasOwnProperty(name)) {
      curr[j++] = name;
    }
  }
  return curr;
};

整體流程是兩趟:第一趟把元素當屬性名塞進物件(重複的自然被吸收),第二趟用 for...in 把屬性名依序撈回陣列。用 hasOwnProperty 過濾是為了排除原型鏈上的屬性。

這個寫法的三個陷阱

  • 型別被字串化:屬性名只能是字串,所以 1 與 '1' 會被視為同一個;[1,2] 與 '1,2' 也會撞在一起。對純數字陣列沒問題,混合型別就要小心。
  • undefined / null 類值:res[temp] 為 falsy 的判斷對某些值不準確,建議改用 hasOwnProperty 判斷存在性。
  • 順序:for...in 的遍歷順序在舊引擎上不保證,數值型屬性名還會被提前排序,這也是為什麼範例輸出是 [0,4,5,8,78,90,a,b] 而不是原始順序。

今天的標準答案

// ES6 Set,簡短且保序
var arr = [0, 8, 5, 4, 78, 8, 90, 4, 'a', 'b', 'a'];
var unique = [...new Set(arr)];

// 或用 filter + indexOf
var unique2 = arr.filter(function (v, i) { return arr.indexOf(v) === i; });

Set 版本時間複雜度 O(n)、保留原始順序、型別判斷正確,是目前的首選。

延伸題:掛到 Array 原型上

變種題目要求「在 Array 類別上新增一個方法,任何陣列呼叫後都能去重」。這題除了去重本身,還考驗對 prototype 與 this 的理解:

Array.prototype.unique = function () {
  var seen = {};
  var result = [];
  for (var i = 0; i < this.length; i++) {
    var key = typeof this[i] + ':' + this[i];   // 加上型別前綴避免碰撞
    if (!seen[key]) { seen[key] = true; result.push(this[i]); }
  }
  return result;
};

不過要提醒:擴充內建原型容易與第三方套件或其他開發者的實作衝突,實務上建議定義成獨立工具函式,而非掛在 Array.prototype 上。

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