从 JavaScript 中的数组中删除重复项

如果您已经了解 javascript 数组的基础知识，那么是时候通过更高级的主题将您的技能提升到一个新的水平。在本系列教程中，您将探索在 JavaScript 中使用数组进行编程的中级主题。

在这篇文章中，我们将处理 javaScript 中数组的一个常用功能：如何删除重复项。有多种删除数组重复项的方法，我将在本教程中向您展示每一种方法。

您将学习如何从基元数组中删除重复项，以及如何以正确的方式从对象数组中删除重复项。 

以下是我们将介绍的方法的摘要：

使用 Set 从数组中删除重复项

这是我们最喜欢的从数组中删除重复项的方法之一。首先，你应该知道 aSet是什么。ASet是ES6中引入的重要数据对象。它只能存储唯一值。在将数组转换为集合的那一刻，它将删除所有重复项。使用Set删除重复项涉及两个阶段：

1. Set使用数组的值 创建一个新的。

2. 将后面转换Set成数组。为此，您可以使用扩展运算符或Array.from函数。

1    const array = [1,1,2,3,2,2,1]    
2    
3    //Step 1     
4    const newSet = new Set(array)    
5    
6    //Step 2     
7    const uniqueArray = [...newSet]    
8    //or     
9    const uniqueArray = Array.from(new Set(array))    
10    
11    console.log(uniqueArray) // [1,2,3]

使用的时间复杂度Set

从现有数组创建集合的时间复杂度为O(N)，即它与数组的长度成正比。Set那是因为现实世界中 JavaScript 实现的内部实现使用了像哈希表这样的高效数据结构。这比许多其他从数组中删除重复项的方法要快得多。

使用的缺点Set

您Set只能使用原始值。当您要从对象数组中删除重复项时，Set 不起作用。如果您想要一种从对象数组中删除重复项的有效方法，请滚动到这篇文章的底部。

使用filter删除数组中的重复项

filter是从数组中删除重复项的最古老的方法之一。在我们了解过滤器的工作原理之前，您需要了解该indexOf方法。该indexOf方法用于查找数组中任何项目的第一个索引。我们将在函数内部使用这个逻辑filter。

1. 使用 方法迭代数组中的每个元素filter。filter 方法返回一个新数组，其中仅包含在辅助函数中返回 true 的元素。

2. 过滤器将调用每个项目及其索引的辅助函数。接下来，我们使用该方法搜索以查看该项目是否出现在数组中的较早位置indexOf。当indexOf返回的值与传递给辅助函数的索引不同时，就会发生这种情况。

3. 如果indexOf在数组中找到该项目的另一个实例，false则从辅助函数返回。这将告诉过滤器不要将当前项目包含在过滤后的数组中。

4. 否则，该项目不是重复项，辅助函数可以返回true。 

1    const array = [ 1, 2, 1, 4, 2, 3];    
2    
3    const newArray = array.filter((item, index) => {    
4      return array.indexOf(item) === index;    
5    });    
6    
7    console.log(newArray) // [1,2,4,3]

下表可帮助您了解逻辑的工作原理：

使用过滤器的时间复杂度

使用过滤器删除重复项的时间复杂度为O(n 2 )。对于短数组，这是删除重复项的简单方法，但随着数组变长，它会比使用Set.

使用reduce 删除数组中的重复项

另一个从数组中删除元素的有趣方法是reduce. 在这里，我们也可以使用该indexOf功能。但是，我们将尝试另一种称为includes. 

如果您不知道它是如何工作的，Reduce 可能会相当棘手。因此，让我通过分解整个过程来帮助您。每个 reduce 辅助函数都有一个累加器和一个当前项。对于每个操作，我们可以选择将另一个项目添加到累加器中，或者跳过。在我们的例子中，伪代码如下。

1. 使用 遍历数组中的每个项目reduce。

2. 辅助函数将传递两个参数：累加器（唯一项数组）和当前项。

3. 如果累加器已经有当前项，则不加修改地返回累加器。我们使用该includes函数来执行此检查。

4. 否则，将该项目插入累加器并返回。

1   const array = [1, 1, 2, 4, 2, 3];    
2    
3    const newArray = array.reduce((unique, item) => {    
4      return unique.includes(item) ? unique : [...unique, item];    
5    }, []);     
6    
7    console.log(newArray) // [1,2,4,3]

使用 Reduce 的时间复杂度

使用删除重复项的时间复杂度reduce为O(n 2 )。通常，在任何数组上运行 reduce 的时间都是O(n) 。Array.includes但是，我们正在为辅助函数内的每个元素执行reduce，这使得整体时间复杂度增加到O(n 2 )。

使用嵌套循环从数组中删除重复项

现在，我们将看看使用forEach循环和find函数删除重复项的经典方法。 

使用嵌套循环的伪代码

1. 创建一个名为的新数组unique来存储没有重复的值。

2. 使用 方法遍历数组forEach。 

3. find在每次迭代中使用该方法forEach来检查当前项是否已存在于数组中unique。如果当前项目不存在，insert它。

1    const array = [1,3,4,1,2,3,4,1]    
2    
3    function removeDuplicates(inputArray) {    
4      const unique = [];    
5      inputArray.forEach(item => {    
6        const isFound = unique.find(inputItem => item === inputItem);    
7        if (!isFound)     
8          unique.push(item);    
9      });    
10      return unique;    
11    }    
12    
13    console.log(removeDuplicates(array)) // [1,3,4,2]

使用嵌套循环的时间复杂度

该removeDuplicates方法调用unique.find()输入数组中的每个元素。同样，这使得整体时间复杂度为O(n 2 )。

使用哈希从数组中删除重复项

如您所见，除了Set技术之外，从数组中删除重复项的所有方法都具有O(n 2 )时间复杂度。不适合更大的数据集。

现在，我们要做一些有趣的事情。让我们编写一个自定义函数，它以O(n)的时间复杂度删除重复项。我们将利用对象实际上是哈希映射这一事实。从对象访问任何值的时间复杂度是O(1)。这是伪代码：

1. 创建一个临时对象来跟踪现有项目和一个数组来收集唯一项目。

2. 使用 遍历数组forEach。

3. 通过检查当前项是否作为键存在于临时对象中来测试当前项是否已被先前找到。 

4. 如果没有，创建一个，并将项目推入 array unique。

1    function removeDuplicates(inputArray){    
2      const unique = [];    
3      const obj = {};     
4      inputArray.forEach(item => {    
5        if (!obj[item]) {     
6          unique.push(item);    
7          obj[item] = item;    
8        }    
9      });    
10      return unique;    
11    }

使用哈希的时间复杂度

此处删除重复项的时间复杂度为O(n)，比仅使用数组方法的其他技术要好得多。当然，就像使用 Set 一样，此方法仅适用于原始值，不适用于对象。

从对象数组中删除重复项

如果您需要从对象数组中删除重复项怎么办？这是其他方法无法很好解决的常见用例。

不过，这并不难。我们将使用上面高效的基于散列的函数，做一个小改动：

1    function removeDuplicatesByKey(inputArray, keyFunction){    
2      const unique = [];    
3      const obj = {};     
4      inputArray.forEach(item => {    
5        let key = keyFunction(item)    
6        if (!obj[key]) {     
7          unique.push(item);    
8          obj[key] = item;    
9        }    
10      });    
11      return unique;    
12    }

这使用相同的基于散列的比较测试来确定每个项目是否是唯一的。但这一次，我们将使用自定义键来跟踪项目。如果两个项目具有相同的键，则可以认为它们相同。参数keyFunction使之成为可能。它是一个辅助函数，它接受一个项目并返回该项目的键。

但是用什么作为密钥呢？这取决于您正在处理的具体数据。但是有几个常见的选择。 

使用 Id 字段作为键

这可能是最常见的解决方案。如果对象有一个唯一标识字段——即一个 id——我们就可以使用它作为键。

1   const array = [{id:1, name: 'a'},{id:2, name: 'b'},{id:1, name: 'a2'} ]    
2    
3    const idKey = (item) => item.id;    
4    const uniqueArray = removeDuplicatesByKey(array, idKey);    
5    
6    console.log(uniqueArray) //[{id:1, name: 'a'},{id:2, name: 'b'}]

JSON.stringify作为钥匙使用

您也可以使用JSON.stringify(). 这是一个通用的解决方案，它不需要数据项具有唯一的 ID。这个想法是使用每个项目的 JSON 表示作为键。这有效地对每个项目的对象结构进行了深入比较，并且仅当项目具有相同的对象结构和值时才会将它们识别为相等。

1    const array = [{x:1, y:1}, {x:2, y:1}, {x:1, y:2}, {x:1, y:1}]    
2    
3    const jsonKey = (item) => JSON.stringify(item);    
4    const uniqueArray = removeDuplicatesByKey(array, jsonKey);    
5    
6    console.log(uniqueArray) //[{id:1, name: 'a'},{id:2, name: 'b'}]

结论

在这篇文章中，我们看到了多种从 JavaScript 数组中删除重复项的方法。当数组变大时，使用散列的方法有更好的性能。但是，也可以仅使用内置Array方法删除重复项。 

最后，如果您需要从对象数组中删除重复项，您可以为每个项目定义一个键并使用它从列表中过滤出重复项。