c++ - 两个向量的并集

Question

我有包含数字 1,7,9,9,3,13,3 的向量 A 我有包含数字 9,11,7,7,3,2,1 的向量 B

我需要获取向量 C，它将包含下面两个向量中的每个元素，但每个元素只有一次（例如向量 A 中的数字 9 不应重复），因此 C 应包含 1、7、9、3、13、11、2

此代码将生成向量 C，它将是两个向量的并集，但会有一些重复的数字（如果一个向量包含 3x 数字 1，则 C 也包含 3x 数字 1）

vector<int>union(vector<int>A,vector<int>B)
{ 
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    vector<int> C(A.size()*2);            //vector A has same size as vector B

    vector<int>::iterator it= set_union(A.begin(),A.end(),B.begin(),B.end(),C.begin());
    C.resize(it-C.begin());
    return C;
}

它必须尽可能快地工作。这样做的最好方法是什么？

Answer 1

这个问题的正确解决方案是先对每个向量进行排序，然后以类似于sink排序的方式进行交集/并集/过滤。