JavaScript:删除数组中的重复项

JavaScript: Removing duplicates in an array of arrays

本文关键字：删除 数组 JavaScript      更新时间：2023-09-26

当前使用JavaScript，我需要遍历一个数组数组，以确定是否有重复的数组，然后删除那些重复的数组。在这种情况下，运行时是至关重要的，所以我想知道最有效的方法是什么

在这种情况下，是否需要使用哈希表？这样做的范围是对每个序列进行散列，然后使用散列来确定该序列是否再次出现。因此，每个序列都是主阵列中的一个阵列，任何重复序列都是同一阵列中的其他阵列。此外，非常重要的是，所有单个阵列本身都保持有序（即，单个阵列中的元素必须始终保持其位置）。此外，单个数组中的所有元素都是字符串值。

示例：假设有一个数组A，其元素依次为以下数组：

A[0] = ["one", "two", "three", "four"]
A[1] = ["two", "one", "three", "four"]
A[2] = ["one", "two", "three", "four"]

在上面的例子中，A[0]和A[2]是重复的，因此函数应该返回A[0]和A+1]，这样同一数组只有一个实例。

保留一个对象，其中键是每个数组的连接元素。如果找不到键，则将数组添加到输出数组，并将键添加到对象。

var hash = {};
var out = [];
for (var i = 0, l = A.length; i < l; i++) {
  var key = A[i].join('|');
  if (!hash[key]) {
    out.push(A[i]);
    hash[key] = 'found';
  }
}

DEMO

好的，让我们先来看看天真解决方案的复杂性：如果有n个数组，每个数组最多有k个条目，则需要O(n^2 * k)比较，因为对于这n个数组中的每一个，都必须将其与n-1个其他数组进行比较，每个数组都有k个比较。空间复杂度为O(n*k)

因此，如果你愿意用空间换取更好的性能，你可以做以下几点：（简短的免责声明：我假设您的所有阵列都有相同数量的k个元素，这是您的问题所指示但未批准的。）

逐个遍历数组，选择第一个元素，我们假设它是a。使用哈希映射来验证您以前是否将此元素视为第一个元素。如果不是，请创建一个以a为根的树结构，将其存储在哈希图中的a下，并使其成为当前节点。现在，对于当前数组中的每个后续条目，您将检查当前节点是否具有该类型的子节点。因此，如果第二个条目是b，则添加b作为的子项

你的树现在看起来是这样的：（从左到右：根到子）

a-b

将c作为第三个条目的工作原理完全相同：

a-b-c

现在我们跳到前面来查看一个数组[a, c, d]。您第一次遇到元素a的树。对于第二个元素，您检查c是否已经是a的子元素。如果不是，请添加它：

  - b - c
a
  - c

下一个条目也是如此：

  - b - c
a
  - c - d

现在让我们看看当我们检查之前看到的阵列时会发生什么：[a, b, c]

首先，我们检查a，看看已经有一个树，并从哈希图中获取它。接下来，我们注意到a有一个名为b的子级，因此我们下降到b。现在，对于最后一个条目，我们看到它也已经在那里了，告诉我们我们遇到了一个可以丢弃的重复项。

很抱歉这是我即兴画的，我希望我能把这个想法传达出去。它只需要遍历每个阵列一次，并以非冗余的方式存储它。因此时间复杂度为O(n*k)。使用的空间增加，但受O(n*k)的限制，因为最坏的情况是没有阵列共享任何前缀，这导致了相同的空间复杂性。

希望我没有忽略什么。

ONELINER

A.filter((r={},a=>!(r[a]=++r[a]|0)))

我假设您的字符串不包含,字符。如果包含，则将两次r[a]更改为r[a.join('|')]（其中|是任意分隔符）或使用r[a.map(x=>x.length+','+x)]允许字符串中的所有字符。这是一个工作示例。

解释

在r={}中，我们设置了一个临时对象。在筛选函数a=>...中，仅用于在参数r={}中声明一次空的临时对象。在a中的函数a=>...中，我们有当前的A元素。JS使a隐式转换为r[a]中的字符串。然后在!(r[a]=++r[a]|0)中，我们增加出现元素a的计数器，如果元素a第一次出现，则返回true（作为滤波器函数值）。

相关文章：