0

我有一个关于如何有效地搜索两个容器以找到相同项目的问题。

例如，我有two list A, B，并且我想找出列表 B 中列表 A 的所有匹配项。

在这种情况下，我需要有两个循环，一个在另一个里面。这不好，因为对于A的每一项，我都会在B中进行整个搜索。

你有一些想法或标准库（提升是可以的）来解决它；）？

非常感谢！

4

5 回答 5

4

您可以std::sort()使用容器std::set_intersection()（我不完全确定该算法的名称）。复杂性将O(n ln n + m ln m)不是序列O(n * m)的大小而是序列的大小。nm

于 2013-11-06T12:27:14.340 回答
4

正如您从不同的答案中看到的那样，有多种方法。这些中的任何一个都可能是正确的，具体取决于您的容器是什么以及范围是否已排序、范围的典型大小以及是否可以选择对范围进行排序。

  • 如果两个容器都排序，std::set_intersection是最好的方法，它的复杂性是O(n+m)
  • 对大小为 n 的容器进行排序O(n log(n))在比较和交换方面具有复杂性。对列表进行排序意味着交换列表节点，这很便宜。对向量进行排序意味着实际上交换了元素，并且成本取决于元素类型。
  • 对于一个已排序和一个未排序的容器，最好对std::binary_search已排序范围内未排序范围的每个元素执行一次。其复杂性在于未排序的排序范围O(n log(m))的大小。首先对未排序的范围进行排序，然后再使用，其复杂性会更差。nmset_intersectionO(n log(n) + m)
  • 有两个未排序的容器，将其中一个排序然后申请binary_search另一个容器的元素是值得的，复杂度为O((m+n) log(m))，因此如果两个容器具有相同的类型，则对较小的容器进行排序会更好。
于 2013-11-06T13:06:54.287 回答
3

如果您有两个列表 A（大小 n）和 B（大小 m），则使用嵌套循环查找 B 中存在于 A 中的每个元素是 O(nm)。

我建议使用hash set。如果您使用 B 中的元素构建一个哈希集，您将花费 O(m) 构建该集合，然后 O(n) 在 hash_set(B) 中查找 A 的每个元素。所以复杂度是 O(n+m)

于 2013-11-06T12:29:54.513 回答
0

也许您可以先对数组中的 A 和 B 进行排序。然后计算相同的元素。它是 O(n*log(n))，但需要更多空间。

于 2013-11-06T12:29:27.513 回答
0

如果您希望优化解决方案，您应该分享有关问题域的更多信息。例如，如果您知道列表中的所有项目都是 1 到 100 之间的整数，您可以使用简单的布尔数组 [100]，并通过在 A 上运行一次（引发适当的标志）然后再运行一次来​​完成任务在 B 上（测试标志）。

如果列表具有任意内容，则您必须满足于通用解决方案。天真的解决方案是像你建议的那样有一个双循环，这不一定那么糟糕。您可以进行一些实际的优化：

  1. 外部循环应该在较短的列表上完成（前提是您知道它们的长度）。这意味着一旦您找到您的项目（如果您找到它......），您的内部循环就会中断。
  2. 如果内存不是问题，您可以对两个列表进行排序，然后并行处理这两个列表，只要另一个列表的项目更大（就像您在它们之间进行排序合并），就在一个列表上前进。这有一个数量级的 O(NlogN+MlogM+max(N,M))，这可能比 O(N*M) 更好，但在内存方面也很浪费。
于 2013-11-06T12:32:29.487 回答