检查集合数组中重复项的更有效方法是什么

Question

鉴于此输入：

const set1 = new Set([10, "someText", {a: 1, b: 2}]);
const set2 = new Set([10, "someText", {a: 1, b: 2}]);
const set3 = new Set([5, "someText", {a: 3, b: 4}]);
const arr = [set1, set2, set3];

combineDupSets(arr);

想要的结果：

[
  Set { 10, 'someText', { a: 1, b: 2 } },
  Set { 5, 'someText', { a: 3, b: 4 } }
]

我正在编写一个函数来消除所有重复集，并且由于 Set() 在它是对象或设置自身时不会检查重复项，因此我编写了以下内容：

function combineDupSets(arr) {
  const hold = [];

  arr.forEach(set =>{
    const copySet = [...set];
    const stringify = JSON.stringify(copySet);
    if(hold.indexOf(stringify) === -1) {
      hold.push(stringify)
    }
  })


  const end = hold.map(item => JSON.parse(item));

  const res = end.map(item => item = new Set(item))

  return res;
}

在这里，我必须使用 3 个大小为 O(n) 的数组来检查这个，我只是想知道是否有任何其他可读的解决方案可以更有效地检查时间和 space复杂度？

谢谢

Answer 1

与其在数组中使用 indexOf，不如考虑将集合放到一个对象或 Map 上，其中键是字符串化的集合，值是原始集合。假设值是有序的：

function combineDupSets(arr) {
   const uniques = new Map();
   for (const set of arr) {
      uniques.set(JSON.stringify([...set]), set);
   }
   return [...uniques.values()];
}

这个

迭代 arr (O(n))
迭代一次内部的每个项目（总共 O(n * m) - 没有回避）
迭代创建的Map并将其放入数组中(O(n))

如果设置值不一定按顺序排列 - 例如，如果您有

Set([true, 'foo'])
Set(['foo', true])

这应该被认为是相等的，然后它会变得更加复杂，因为每个 Set 中的每个项目不仅必须迭代，而且还要与 中的每个其他项目进行比较以某种方式设置。实现这一点的一种方法是按字符串化值排序：

function combineDupSets(arr) {
   const uniques = new Map();
   for (const set of arr) {
      const key = [...set].map(JSON.stringify).sort().join();
      uniques.set(key, set);
   }
   return [...uniques.values()];
}

Answer 2

您可以迭代集合并检查值，并且仅当对象共享相同的对象引用时才将对象视为相等。

function combineDupSets(array) {
    return array.reduce((r, s) => {
        const values = [...s];
        if (!r.some(t => s.size === t.size && values.every(Set.prototype.has, t))) r.push(s);
        return r;
    }, []);
}

const
    a = { a: 1, b: 2 },
    b = { a: 3, b: 4 },
    set1 = new Set([10, "someText", a]),
    set2 = new Set([10, "someText", a]),
    set3 = new Set([5, "someText", b]),
    arr = [set1, set2, set3];

console.log(combineDupSets(arr).map(s => [...s]));

检查集合数组中重复项的更有效方法是什么

What is a more efficient way to check for duplicates in an array of sets

javascript

arrays

duplicates

set

space-complexity