n 个向量的交集

我是编程新手，最近遇到了一个问题，即查找已排序整数的 n 个向量（整数向量）的交集。我想出的方法的复杂度为 O(n^2)，并且我正在使用 std::set_intersect 函数。

我想出的方法是使用两个向量：第一个向量对应于我拥有的第一个向量，第二个向量对应于第二个向量。我对两个向量调用设置交集并覆盖第一个向量，然后对第二个向量使用向量清除函数。然后，我将下一个向量覆盖为第二个向量，并重复该过程，最终返回第一个向量。

我确实相信有一种更有效的方法来解决这个问题，但目前我想不出更有效的方法。任何有关这个问题的帮助将不胜感激。

幸运的是，我认为可以对 算法的复杂性。

复杂度std::set_intersection在大小为 n1 和 n2 的输入集上是 O(n1 + n2)。 您可以采用原始向量并以单淘汰法将它们相交 锦标赛风格，即在第一轮中，第一轮和第二轮相交 向量，第3个和第4个，第5个和第6个，依此类推；在 第二轮你与第一个和第二个交叉点相交，第三个和第四个交叉点， 等等；重复直到最后一轮仅产生一个交叉点。 每轮幸存的所有向量的大小总和不超过 本轮开始时向量大小总和的一半， 所以这个算法总共需要 O(N) 时间（也是 O(N) 空间） 其中 N 是输入中所有原始向量大小的总和。 （这是 O(N)，因为 N + N/2 + N/4 + ...

因此，给定一个由已排序向量组成的输入， 算法的复杂度为O(N)。

你的算法以非常不同的顺序合并向量， 虽然我不能 100% 确定它也是 O(N)，但我强烈怀疑它是 O(N)。

Edit:关于如何在 C++ 中实际实现“锦标赛”算法， 这取决于你想多努力地优化它， 以及您输入的性质。

最简单的方法是创建一个新的向量列表；从旧列表中取出两个向量，将一个向量推入新列表，将两个旧向量合并到新向量上，销毁旧向量，希望库能够有效地管理内存。

如果你想减少新向量的分配，那么重新使用向量 （正如您已经想到的那样）可能会有所帮助。如果输入数据结构是 一个std::list<std::vector<int> >例如，您可以首先将一个空向量推到该列表的前面。创建三个迭代器，一个迭代器指向新向量，一个迭代器指向列表中原始的前两个向量。 取最后两个迭代器处向量的交集， 将结果写入第一个迭代器，然后清除第一个迭代器处的向量 最后两个迭代器。将最后两个迭代器各向前移动两位， 将第一个迭代器向前移动一个位置。重复。如果你达到这样的状态 最后两个迭代器之一已到达 end() 但另一个尚未到达， 删除第一个迭代器和另一个迭代器之间的所有列表元素。 现在你又得到了一个向量列表，并且只要有就可以重复 列表中存在多个向量。

如果输入是std::vector<std::vector<int> >然后推入一个元素 放在列表前面的价格相对昂贵，因此您可能想要一个 算法稍微复杂一些。有很多选择，其实没有 我能想到的明显的赢家。