萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 陣列去重三大經典演算法:雙層迴圈、排序比鄰、Hash Map(Set)完整比較

前言

陣列去重是前端高頻考題與實務需求。本文系統整理三種經典演算法,從原理、代碼、效能、優缺點到適用場景全方位解析。

方法一:雙層迴圈(O(n²))—— 最直觀

Array.prototype.unique1 = function () {
  const res = [this[0]];
  for (let i = 1; i < this.length; i++) {
    let repeat = false;
    for (let j = 0; j < res.length; j++) {
      if (this[i] === res[j]) { repeat = true; break; }
    }
    if (!repeat) res.push(this[i]);
  }
  return res;
};
  • ✅ 保持原順序
  • ✅ 使用 `===` 比較,正確區分 `1` vs `"1"`、物件參考
  • ❌ 效能差,>1萬筆明顯卡頓

方法二:排序後比較相鄰(O(n log n))—— 較快但改變順序

Array.prototype.unique2 = function () {
  const sorted = [...this].sort(); // 複本排序,不汙染原陣列
  const res = [sorted[0]];
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] !== res[res.length - 1]) res.push(sorted[i]);
  }
  return res;
};
  • ✅ 效能大幅優於方法一
  • ❌ **結果為排序後順序**,非原順序
  • ❌ 預設 `sort()` 按字串序,數字 `[10, 2]` 會排錯,需自訂比較函式
  • ❌ 物件/函式無法直接比較

方法三:Hash Map / Set(O(n))—— 現代首選

Array.prototype.unique3 = function () {
  const res = [];
  const seen = {}; // 或 new Set()
  for (let i = 0; i < this.length; i++) {
    const val = this[i];
    if (!seen[val]) { // 注意:鍵會被轉字串,1 與 "1" 會衝突
      res.push(val);
      seen[val] = 1;
    }
  }
  return res;
};

改良版:區分型別(1 ≠ "1")

Array.prototype.unique3Typed = function () {
  const res = [];
  const seen = new Map(); // Map 鍵保持原型別
  for (const val of this) {
    const key = typeof val + ":" + val; // 簡易鍵
    if (!seen.has(key)) {
      res.push(val);
      seen.set(key, true);
    }
  }
  return res;
};

ES6 極簡版(基本型別 + 物件參考去重)

const unique = arr => [...new Set(arr)];

效能與特性對照

方法時間複雜度保持順序型別區分物件去重推薦指數
雙層迴圈O(n²)✅✅參考比較⭐ (教學用)
排序比鄰O(n log n)❌❌ (1=="1")❌⭐⭐ (舊環境)
Object/MapO(n)✅✅ (加前綴)參考比較⭐⭐⭐⭐
SetO(n)✅✅ (SameValueZero)參考比較⭐⭐⭐⭐⭐ (現代首選)

進階:深度內容去重(物件值相等視為重複)

function uniqueDeep(arr) {
  const seen = new Set();
  return arr.filter(item => {
    const key = JSON.stringify(item); // 簡易序列化
    if (seen.has(key)) return false;
    seen.add(key);
    return true;
  });
}
// ⚠️ 局限:無法處理函式、循環引用、屬性順序不同但內容相同

總結建議

  1. 現代專案:直接用 `[...new Set(arr)]`,簡潔高效。
  2. 需區分 1/"1":用 `Map` + 型別前綴鍵。
  3. 舊環境無 ES6:用 `Object.create(null)` 做 Hash Map。
  4. 複雜物件內容去重:評估資料量,小量用 `JSON.stringify` + Set,大量考慮正規化 ID 去重。
copyright © 萬盛學電腦網 all rights reserved