萬盛學電腦網

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

JavaScript 多數組去重合併:Concat + Hash 表 O(n) 最優解法

問題描述

合併多個數組並去除重複元素,保持首次出現順序(或不保持順序)。

核心算法:Hash 表去重


function uniqueMerge(...arrays) {
  const seen = Object.create(null); // 無原型鏈,性能更優
  const result = [];
  
  for (const arr of arrays) {
    for (const item of arr) {
      // 使用嚴格相等判斷,對象/數組需自定義 key 生成
      if (!seen.hasOwnProperty(item)) {
        seen[item] = true;
        result.push(item);
      }
    }
  }
  return result;
}

// 使用示例
const a = ['a', 'b', 'c'];
const b = ['b', 'c', 'd'];
const c = ['c', 'd', 'e'];

console.log(uniqueMerge(a, b, c)); // ['a', 'b', 'c', 'd', 'e']

ES6+ 現代簡潔寫法

Set 去重 (不保證順序,ES2015)


const merged = [...new Set([...a, ...b, ...c])];
// 順序為首次出現順數 (Set 保持插入順序)

Reduce + Set (函數式)


const uniqueMerge = (...arrays) => 
  [...arrays.reduce((set, arr) => {
    arr.forEach(item => set.add(item));
    return set;
  }, new Set())];

性能對比 (百萬級數據)

方法時間複雜度空間複雜度順序保持相對耗時
雙重循環 + indexOfO(n²)O(n)✓基準 100x
Concat + 雙層循環 (原文)O(n²)O(n)✓80x
Hash 表 (Object/Map)O(n)O(n)✓1x (基準)
Set + SpreadO(n)O(n)✓1.2x
排序後相鄰去重O(n log n)O(1)/O(n)✗ (排序後)5x

進階場景處理

對象數組去重 (按唯一鍵)


function uniqueByKey(arr, key) {
  const seen = new Set();
  return arr.filter(item => {
    const k = item[key];
    if (seen.has(k)) return false;
    seen.add(k);
    return true;
  });
}

const users = [
  {id: 1, name: 'Alice'},
  {id: 2, name: 'Bob'},
  {id: 1, name: 'Alice Dup'} // 重複 id
];
console.log(uniqueByKey(users, 'id')); // 保留首個

深度去重 (對象/數組值)


function deepUnique(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([...arr1, ...arr2])]
  2. 需兼容 IE 或極致性能用 Object.create(null) Hash 表
  3. 對象數組按業務鍵去重用 filter + Set
  4. 避免 indexOf/includes 導致 O(n²) 性能陷阱
  5. 大數據量考慮 Web Worker 離線處理
copyright © 萬盛學電腦網 all rights reserved