从对象数组中删除重复项的更好算法是什么？

Question

我有一个对象数组，看起来像（粗略的例子）：

[{id:1, stuff:moreStuff}, {id:6, manyStuff,Stuffing}, {id:4, yayStuff, stuff}, {id:6, manyStuff, Stuffing}]

问题是在数组中，有几个重复的对象。到目前为止我想到的当前解决方案是这样的：

const DuplicateCheck = []
const FinalResult = []

for (let i = 0; i < ArrayOfObjects.length; i++) {
    let isPresent = false;
    for (let j = 0; j < duplicateCheck.length; j++) {
        if (ArrayOfObjects[i].id == duplicateCheck[j]) {
            isPresent = true;
        }
    }
    if (isPresent = false) {
        DuplicateCheck.push(ArrayOfObjects[i].id
        FinalResult.push(ArrayOfObjects[i]
    }
}

现在学习了大O之后，似乎这是解决这个问题的一种非常低效的方法。所以我的问题是，有没有更好、更有效的方法来解决这个问题？

Answer 1

您可以保留 usedIds 作为对象属性并仅在对象没有这样的属性时才添加到过滤后的数组中，或者如果可能的话，只需将您的项目添加到 Set 中你。设置为数据结构只能存储不重复的。

没有设置:

const filteredArray = [];
const usedIds = {};

for (const item of array) {
  if (!usedIds[item.id]) {
    usedIds[item.id] = true;
    filteredArray.push(item);
  }
}

含套装:

const filteredArray = [];
const usedIds = new Set();

for (const item of array) {
  if (!usedIds.has(item.id)) {
    usedIds.add(item.id);
    filteredArray.push(item);
  }
}

可运行示例：

const array = [
  {
    id: 1,
    stuff: 'stuff',
    moreStuff: 'moreStuff'
  },
  {
    id: 6,
    manyStuff: 'manyStuff',
    stuffing: 'stuffing'
  },
  {
    id: 4,
    yayStuff: 'yayStuff',
    stuff: 'stuff'
  },
  {
    id: 6,
    manyStuff: 'manyStuff',
    stuffing: 'stuffing'
  }
];

const filteredArray = [];
const usedIds = {};

for (const item of array) {
  if (!usedIds[item.id]) {
    usedIds[item.id] = true;
    filteredArray.push(item);
  }
}

console.log(filteredArray);

Answer 2

是的，为您的 DuplicateCheck 使用 Set，这样您就可以通过 id:

访问 O(1)

const duplicateCheck = new Set
const finalResult = []

for (const object of arrayOfObjects) {
    if (!duplicateCheck.has(object.id)) {
        duplicateCheck.add(object.id)
        finalResult.push(object)
    }
}

Answer 3

您可以遍历数组并将 id 存储在对象（哈希 table）中，然后检查是否存在。类似于：

const DuplicateCheck = {}
const FinalResult = []

for (let i = 0; i < ArrayOfObjects.length; i++) {
    let currentId = ArrayOfObjects[i].id

    if (!DuplicateCheck[currentId]) {
        DuplicateCheck[currentId] = 1
        FinalResult.push(ArrayOfObjects[i])
    }
}

您将在 FinalResult 中收到所有唯一对象

Answer 4

您也可以使用 Map to filter out duplicates. Contrary to the 此解决方案会留下副本的最后一个版本，因为它会使用相同的密钥覆盖 key/value-pair。

const objectsById = new Map(arrayOfObjects.map(object => [object.id, object]));
const finalResult = Array.from(objectsById.values());

上面的代码确实需要迭代集合 2 次。一次使用 map 创建 key/value-pairs 一次，当创建的数组转换为 Map.

时

创建结果 objectsById 后，我们必须迭代这些值以将它们转换回数组。

总的来说，这意味着对整个集合进行 2 到 3 次迭代，这通常比使用 find 的解决方案快很多。因为每次调用时都会遍历数组。

如果省略 map 调用并在 objectsById:

中手动插入元素，则可以将迭代次数减少 1

const objectsById = new Map();
for (const object of arrayOfObjects) {
  objectsById.set(object.id, object);
}

从对象数组中删除重复项的更好算法是什么？

What's a better algorithm to remove duplicates from an array of objects?

javascript

arrays

big-o

object

duplicates