我是编程新手,最近遇到了一个问题,即查找已排序整数的 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> >
然后推入一个元素
放在列表前面的价格相对昂贵,因此您可能想要一个
算法稍微复杂一些。有很多选择,其实没有
我能想到的明显的赢家。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)