C++数组交集

Question

有谁知道是否可以将其从O(m*n)转为O(m + n)？

    vector<int> theFirst;
    vector<int> theSecond;
    vector<int> theMatch;

    theFirst.push_back( -2147483648 );
    theFirst.push_back(2);
    theFirst.push_back(44);
    theFirst.push_back(1);
    theFirst.push_back(22);
    theFirst.push_back(1);

    theSecond.push_back(1);
    theSecond.push_back( -2147483648 );
    theSecond.push_back(3);
    theSecond.push_back(44);
    theSecond.push_back(32);
    theSecond.push_back(1);

    for( int i = 0; i < theFirst.size(); i++ )
    {
        for( int x = 0; x < theSecond.size(); x++ )
        {
            if( theFirst[i] == theSecond[x] )
            {
                theMatch.push_back( theFirst[i] );
            }
        }
    }

Answer 1

将第一个向量的内容放入哈希集中,例如std::unordered_set.那是O(m).扫描第二个向量,检查值是否在unordered_set中并保持其中的值.这是哈希结构的n次查找,所以O(n).所以,O(m + n).如果重叠中有l个元素,则可以计算O(l)以将它们添加到第三个向量.std::unordered_set是在C++ 0x草案中,并在最新的gcc版本中提供,并且还有一个实现在boost中.

编辑使用unordered_set

使用C++ 2011语法:

unordered_set<int> firstMap(theFirst.begin(), theFirst.end());

for (const int& i : theSecond) {
   if (firstMap.find(i)!=firstMap.end()) {
     cout << "Duplicate: " << i << endl;
     theMatch.push_back(i);
   }
}

现在,问题仍然存在,你想对原件中的重复做什么？明确地说,多少次应该1是theMatch,1,2或4倍？这输出:

Duplicate: 1
Duplicate: -2147483648
Duplicate: 44
Duplicate: 1