DIV CSS 佈局教程網

javascript 陣列去重總結:從雙層迴圈到物件字典的四種思路
編輯:關於JavaScript     

面試前複習 JavaScript,無可避免會撞上陣列去重這一題。本文把自己整理的四種思路完整記錄下來,包含各自的優缺點與踩過的坑。這個系列不預定篇數、也不保證時效,想到哪寫到哪,純粹談個人理解,若有錯誤歡迎指正。

關於「去重」這件事

陣列去重是演算法考察的熱門題目,實現方式大致可分兩條路:唯一性與非唯一性。講白了就是「挑出只出現一次的」或「刪掉重複出現的」。以下演算法名稱都是我自己隨便取的,請忽略命名。

一、循環匹配去重(雙層迴圈)

顧名思義:把陣列裡每個元素都拿去跟「已存放元素的結果陣列」比一遍,遇到沒出現過的就放進去,直到掃完為止。因為外層與內層都有迴圈,也可以叫雙循環匹配去重——這大概是所有人第一時間都能想到的做法。

var arr = [1, 3, 4, 56, 3, 7, 9, 7];
var result = [];

// 比對是否已存在
function isMatch(array, n) {
  for (var i = 0; i < array.length; i++) {
    if (array[i] === n) {
      return true;
    }
  }
  return false;
}

// 逐一驗證所有元素
function unqiue(array) {
  for (var i = 0; i < array.length; i++) {
    if (!isMatch(result, array[i])) {
      result.push(array[i]);
    }
  }
  return result;
}

console.log(unqiue(arr));

這裡有個容易忽略的 bug:如果陣列裡同時存在數字 1 和字串 '1',用雙等號 == 比較時瀏覽器會做型別轉換,兩者會被誤判為同一個值。改用全等 === 才是正確的:

var arr = [1, 3, 4, 56, 3, '1', 7, 9, 7];
// isMatch 內改用 array[i] === n,即可正確保留 '1'

優點:實作簡單、思路直觀。缺點:效率低落,時間複雜度 O(n²)。

二、JSON/物件/字典去重

原理是利用 Object 的鍵具有唯一性:把陣列元素轉成物件的 key,值存索引,最後用 for...in 把 key 收集回新陣列。由於 Array、JSON 與 {} 本質上都是 Object,三種寫法效果完全相同。

var arr = [1, 3, 4, 56, 3, '1', 7, 9, 7];

function unqiue(array) {
  var cache = {};      // 也可以寫成 [] 或 new Object()
  var result = [];

  // 把元素當成物件的 key
  for (var i = 0; i < array.length; i++) {
    cache[array[i]] = i;
  }

  // key 就是去重後的元素
  for (var key in cache) {
    result.push(key);
  }

  return result;
}

console.log(unqiue(arr));

優點:簡單,效率非常高。缺點:一是改變了元素型別——物件的 key 一律是字串,原本的數字 1 出來會變成 '1';二是無法區分數字與數字形式的字串,兩者會被視為同一個鍵。

三、隊列遞歸去重

思路是先把陣列排序成升序或降序的「隊列」,這樣相同的值自然就挨在一起;然後從尾端往前逐一比對,若與前一格相同就刪掉尾端,再繼續往前。全部掃完,剩下的就是去重後的結果。

var arr = [6, 4, 6, 9, '6', 13, 56, 9, '11', 1, 8, '7', 17, 5, 45, 3, 7];

function unqiue(array) {
  // 排序,讓相同元素相鄰
  array.sort(function (m, n) { return m - n; });

  // 從隊尾往前比,相同就刪除
  function loop(index) {
    if (index >= 1) {
      if (array[index] === array[index - 1]) {
        array.splice(index, 1);
      }
      loop(index - 1);
    }
  }

  loop(array.length - 1);
  return array;
}

console.log(unqiue(arr));

優點:效率較高。缺點:不是最快,而且會破壞原始陣列(sort 是原地排序),若原陣列還要繼續使用,記得先 slice() 複製一份。另外遞迴深度等於陣列長度,資料量大時有堆疊溢出的風險,改成迴圈更安全。

四、indexOf 去重與 polyfill

indexOf 是 ECMAScript 5 新增的方法,IE8 及以下不支援(IE8 只實作了部分 ES5),因此在需要相容舊環境時得自己補一個:

if (!Array.prototype.indexOf) {
  Array.prototype.indexOf = function (item) {
    var result = -1, a_item = null;
    if (this.length == 0) {
      return result;
    }
    for (var i = 0, len = this.length; i < len; i++) {
      a_item = this[i];
      if (a_item === item) {
        result = i;
        break;
      }
    }
    return result;
  };
}

有了 indexOf,去重就能寫得非常短:

function unique(array) {
  return array.filter(function (el, index, arr) {
    return index === arr.indexOf(el);   // 只保留第一次出現的位置
  });
}

優點:程式碼極簡。缺點:每個元素都要做一次線性搜尋,整體仍是 O(n²)。

五、那麼該用哪一個?

把上面的分析攤開來看,結論其實很清楚:

若目標環境允許 ES6,[...new Set(arr)] 一行就解決,而且 Set 能正確區分 1 與 '1',也能存放物件參照,語意最乾淨。

若必須相容舊瀏覽器,物件字典法在效能與簡潔度之間最平衡,唯一要記住的是型別會被轉為字串;若元素是物件,就不能直接當 key,得改用「以唯一識別欄位(如 id)組字串當鍵」或 filter + indexOf 搭配自訂比較。

至於雙層迴圈與排序遞歸,效能都不理想,主要價值在於面試時展現思路,以及理解「用空間換時間」這個基本取捨。

最後補一個所有方法都適用的提醒:去重前先確認需求是「保留第一次出現」還是「保留最後一次」,以及要不要保持原始順序。物件字典法與排序法的輸出順序都和原陣列不同,若順序有意義(例如時間序列資料),記得額外處理。

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