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

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

是的，对您的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 2

您可以对数组进行迭代，并将id存储在和对象(哈希表(中，然后检查是否存在。类似于：

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 3

您可以将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 4

您还可以使用Map来过滤重复项。与Bergi的Set方法相反，此解决方案保留了副本的最后一个版本，因为它使用相同的键覆盖键/值对。

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

上面的代码确实需要对集合进行2次迭代。一次使用map创建键/值对，一次当创建的数组转换为Map时。

创建生成的objectsById时，我们必须迭代这些值，将它们转换回数组。

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

如果省略map调用并手动在objectsById:中插入元素，则可以将迭代次数减少1

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