0

我只在这个问题中使用 std::vector 并且每个向量都是有序的，没有重复。现在我想合并具有相同数字的向量。所以 2 3 可以与 3 4 5 联合，但不能与 4 5 或 1 5 联合。

例子：

如果我有以下向量...

1
1
2 3 4
5
1 5
2
4 7

联合之后，我应该只剩下 2 个向量：

1 5
2 3 4 7

代码：

vector<int> a,b,c,d,e,f,g;
vector<vector<int>> myList;

a.push_back(1);
b.push_back(1);
c.push_back(2);
c.push_back(3);
c.push_back(4);
d.push_back(5);
e.push_back(1);
e.push_back(5);
f.push_back(2);
g.push_back(4);
g.push_back(7);

myList.push_back(a);
myList.push_back(b);
myList.push_back(c);
myList.push_back(d);
myList.push_back(e);
myList.push_back(f);
myList.push_back(g);

//this should print out the vectors in my above example
for (int i =0; i<myList.size(); i++) {
    for (int j=0; j<myList[i].size(); j++) {
        cout<<myList[i][j]<<" ";
    }
    cout<<endl;
}

我尝试使用 set_union 和 set_intersection 来实现我的目标，但它没有按预期工作。我怀疑问题出在我没有正确更改的向量大小上。请帮忙。谢谢！

编辑：

这是错误的代码，最初我对联合有问题，但现在它会自动运行..现在我想我主要不确定如何使用 set_intersection 来找出是否有交集

vector<int>::iterator myIt;
vector<int> myTemp;
vector<int> myTemp2;
vector<int> myResult(20);
vector<int> myResult2(20);


while (!myList.empty()) {

    myTemp2 = myList.back();
    myList.pop_back();


    myIt = set_intersection(myTemp.begin(), myTemp.end(), 
                            myTemp2.begin(), myTemp2.end(), myResult.begin());

    //this is checking whether there is intersection but it doesn't work
    if (myResult.size()) {

        myIt = set_union(myTemp.begin(), myTemp.end(), 
                         myTemp2.begin(), myTemp2.end(), myResult2.begin());

        myTemp = myResult2;

    }


}

cout<<"after union: "<<endl;

for (auto it = myResult2.begin(); it != myResult2.end() ; it++) {
    cout<<*it<< " ";
}
4

2 回答 2

1

如果我对您的理解正确，那么不仅您的代码而且您的方法都大错特错。您正在尝试解决连接的组件/不相交的集合类型问题，但是您的方法例如只返回一个vectors int...？它肯定需要返回 a vectorof s。vector<int>

以下代码是我能想到的最接近您的代码，应该可以使用。它应该留下result你想要的输出。

vector< vector<int> > result;

for(int i = 0; i < myList.size(); i++)
{

    bool match = false;
    int matchFirst = -1;

    for(int j = 0; j < result.size(); j++)
    {

        vector<int> myResult;
        vector<int> myResult2;

        set_intersection(myList[i].begin(), myList[i].end(),
                         result[j].begin(), result[j].end(),
                         back_inserter(myResult));

        if (myResult.size())
        {
            set_union(myList[i].begin(), myList[i].end(),
                      result[j].begin(), result[j].end(), back_inserter(myResult2));

            if(match)
            {
                vector<int> myResult3;
                set_union(myResult2.begin(), myResult2.end(),
                          result[matchFirst].begin(), result[matchFirst].end(), back_inserter(myResult3));
                result.erase(result.begin() + j, result.begin() + j + 1);
                result[matchFirst] = myResult3;
                j--;
            }
            else
            {
                matchFirst = j;
                result[j] = myResult2;
                match = true;
            }

        }

    }

    if(!match)
    {
        result.push_back(myList[i]);
    }
}

编辑：修复了一个错误。

于 2013-04-10T23:25:35.980 回答
1

这并不完美

vector<int> myResult(20);

myIt = set_intersection(myTemp.begin(), myTemp.end(), 
     myTemp2.begin(), myTemp2.end(), myResult.begin());

问题是 set_intersection（和 set_union）不会改变向量的大小。通过使 myResult 大小为 20，您为自己提供了足够的空间，但在完成交集后，您仍然会得到一个大小为 20 的向量，因此myResult.size() == 20无论您在两个向量中拥有什么元素开始。

您需要的是使用 set_intersection 的方法，以便将元素添加到目标向量。为此，您需要back_inserter

#include <iterator>

vector<int> myResult;

set_intersection(myTemp.begin(), myTemp.end(), 
    myTemp2.begin(), myTemp2.end(), 
    back_inserter(myResult));

back_inserter使用 将元素添加到向量中push_back，因此 myResult 从大小为零开始，最终以正确的大小结束，具体取决于交点中有多少元素。因此，您可以测试myResult.size() > 0以判断是否有任何共同元素。

当你调用 set_union 时做同样的事情。

于 2013-04-10T22:51:29.970 回答