主页 / 问题 / 749522
Accepted
Pavel Perevezencev
Asked:2020-11-25 23:53:43 +0000 UTC2020-11-25 23:53:43 +0000 UTC

查找数组中的重复序列

  • 772

给定一组具有大约以下内容的数组：

[
  [D6],
  [D5],
  [D5, D6],
  [D3, D6],
  [D4],
  [D4, D6],
  [D4, D5],
  [D4, D5, D6]
  ...
]

有必要从这些数组中找到所有重复序列（大于 2 个元素）。对于上面的例子：

[
  [D6],
  [D5],
  [D5, D6],
  [D3, D6],
  [D4],
  [D4, D6],
  [T1],
  [T1, D6]
  ...
]

最后两个数组包含子集 [D4, D5] => 在子集 [D4, D5] 出现在 T1 的所有数组中发生变化。

首先想到的是生成这些数组元素的所有可能组合，然后遍历数组并查找条目，但在我看来这不是最好的解决方案，如何更优化地解决这个问题？

UPD： 想到的第二件事是寻找数组的交集，但是您必须对每个数组进行迭代，但在我看来，有一个更优化的解决方案

javascript

1 个回答

  1. Best Answer

    你可以这样做。遍历每一行，并将AllVariants这一行中的所有序列写到一个单独的数组中。这将是所有字符串的公共数组。一旦我们在这个公共数组中遇到重复，就意味着我们找到了重复。为了加快工作速度，这个大数组中的key应该是一串按顺序排列的值，例如ACD。并且在值中，您可以编写一个指向使用该值的元素的链接列表，然后您可以快速轻松地进行替换。

    我在评论中描述的问题仍然存在。在一个序列中，例如ABCD，可以有多个与其他序列重复的元素，例如AD和AC，如果我们按照问题的条件进行替换，例如，我们将AD替换为T1 ，那么我们将永远找不到 AC 的重复，因为 A 不再存在。但这不是决定和任务条件的问题。

    • 1

相关问题