我有 2 个向量，其中包含 Person（姓名、姓氏等）对象。我想取其中一个向量（我们将其命名为“大”），然后为该向量中的每个元素找到第二个（“小”）中的对应元素，并将“小”向量元素中的一些数据合并到“大”向量元素。此操作与 SQL 术语中的左连接非常相似，但需要对数据进行额外的合并。最简单的方法是进行 2 个周期，但这会导致 O(n^2) 时间复杂度。我可以用 STL 算法做得更好吗？
问问题
1157 次
3 回答
5
如果对小向量进行排序，则可以通过扫描大向量得到合并部分的 O(n log n) 并使用binary_search查找小向量中的元素。
于 2011-03-04T16:00:27.873 回答
2
是的！您可以在 O(nlogn) 时间复杂度内完成。对第二个向量进行排序，这需要 O(nlogn) 时间。对于第一个向量中的每个元素，使用二进制搜索（STL 具有 binary_search 算法）在第二个向量中找到对应的元素，并将数据合并到第一个向量中的元素。对于第一个向量中的每个元素，我们花费 O(logn) 时间。所以这种方法的运行时间复杂度是O(nlogn)。
于 2011-03-04T16:01:03.560 回答
2
如果您的列表不经常更改，您可以对两个列表进行排序，然后通过简单地遍历两个列表以线性时间进行合并。
如果您的列表一直在变化，您最好对“小”容器进行排序，例如mapor set。在这种情况下，只需find在要加入的大列表中的每个项目上使用。
于 2011-03-04T16:04:50.267 回答