c++ - 2 つのソート済み配列の交差

Question

質問> 2 つの並べ替えられた配列 A と B が与えられた場合、A と B に共通する要素を含む配列 C を返します。配列 C には重複を含めることはできません。

これが私の解決策ですが、それは間違っていると思います。しかし、私はそれを否定する反例を見つけることができません。誰かが私のためにそれを指摘できますか? それとも反例を教えてください。

アップデート：

アルゴリズムは次のように機能します。

各配列へのポインターを 1 つ保持し、共通の要素が見つかるまでこれらのポインターを前方に移動します。次に、共通要素が C にない場合、見つかった要素は C に格納されます。それ以外の場合は、要素に応じてポインタを前方に移動します。

#include <iostream>
#include <vector>
#include <random>
#include <iterator>
#include <algorithm>
using namespace std;

vector<int> Intersect(const vector<int>& vecIntsA, const vector<int>& vecIntB)
{
    int indA = 0;
    int indB = 0;
    vector<int> vecIntC;

    while(indA < vecIntsA.size() && indB < vecIntB.size())
    {
        if (vecIntsA[indA] == vecIntB[indB]) {
            if ( vecIntC.empty() || vecIntC.back() != vecIntsA[indA])
                vecIntC.emplace_back(vecIntsA[indA]);
            indA++;
            indB++;
        } else if (vecIntsA[indA] < vecIntB[indB]) 
            indA++;
        else // (vecIntsA[indA] > vecIntB[indB]) 
            indB++;        
    }

    return vecIntC;
}

int main()
{
   default_random_engine dre;
   uniform_int_distribution<int> dist(0, 100);

   vector<int> vecIntA;
   for(int i=0; i < 20; ++i)
    vecIntA.emplace_back(dist(dre));   
   sort(vecIntA.begin(), vecIntA.end());
   copy(vecIntA.cbegin(), vecIntA.cend(), ostream_iterator<int>(cout, ","));
   cout << endl;

   vector<int> vecIntB;
   for(int i=0; i < 24; ++i)
    vecIntB.emplace_back(dist(dre));   
   sort(vecIntB.begin(), vecIntB.end());
   copy(vecIntB.cbegin(), vecIntB.cend(), ostream_iterator<int>(cout, ","));
   cout << endl;

   vector<int> vecIntC = Intersect(vecIntA, vecIntB);
   copy(vecIntC.cbegin(), vecIntC.cend(), ostream_iterator<int>(cout, ","));

   return 0;
}

Answer 1

STL アルゴリズム set_intersection と unique? をいつでも使用できます。