C++中的向量交集

Question

我有这个函数

vector<string> instersection(const vector<string> &v1, const vector<string> &v2);

我有两个字符串向量，希望找到这两个向量中都出现的字符串，并将它们填充到第三个向量中。

如果我的向量是...

v1 = <"a","b","c">
v2 = <"b","c">

- Tyler

---

对向量进行sort()排序，然后使用单个for循环同时浏览两个向量，始终推进较小的一个。然后只需收集共同的元素即可。 - tp1

通过一个向量进行for循环，然后在其中通过另一个向量进行for循环。 - Agent_L

Answer 1

试用std::set_intersection，例如：

#include <algorithm> //std::sort
#include <iostream> //std::cout
#include <string> //std::string
#include <vector> //std::vector

std::vector<std::string> intersection(std::vector<std::string> v1,
                                      std::vector<std::string> v2){
    std::vector<std::string> v3;

    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::set_intersection(v1.begin(),v1.end(),
                          v2.begin(),v2.end(),
                          back_inserter(v3));
    return v3;
}

int main(){
    std::vector<std::string> v1 {"a","b","c"};
    std::vector<std::string> v2 {"b","c"};

    auto v3 = intersection(v1, v2);

    for(std::string n : v3)
        std::cout << n << ' ';
}

- masoud

---

这是O(n log n)的时间复杂度，其中n是两个向量中较大的一个。为什么不仅仅创建一个哈希集合，包含其中一个向量的条目，然后线性地通过另一个向量检查它们呢？这是O(n + m)的时间复杂度，使用O(m)的内存。我可以看到，我提出的解决方案不太友好于缓存，而且使用更多的内存。 - Eric Auld

我认为OP没有说向量已排序。 - laike9m

Answer 2

你需要对较小的向量进行排序。然后在较大的向量上进行单次遍历，并通过使用二分搜索测试其项在小向量中的存在性。

- Mikhail Volskiy

Answer 3

如果不使用排序，可以通过将较小的向量制作成哈希集，然后循环遍历较大的向量来检查这些元素，如此处所建议的。这比使用std::set_intersection进行排序更快。

- Eric Auld