積集合（共通部分）を求める

面接で出たクイズについてメモを残しておきます。

２つの配列があり、要素はソートされています。その積集合、つまり両方に含まれている要素を探してください。

何も考えずにやると二重ループのO(N^2)になりますが、ポインタを2つ用意して、値が等しければ積集合に追加。そうでないときは値が小さい方を1つ進める。計算量はO(N)といったところです。ソートされていなければソートするので、O(log N)になります。

vector<int> set_intersection( const vector<int> &set1, const vector<int> &set2 )
{
    int s1 = 0;
    int s2 = 0;

    vector<int> result;

    while( s1 != set1.size() && s2 != set2.size() )
    {
        if( set1[s1] == set2[s2] )
        {
            result.push_back(set1[s1]);
            s1++;
            s2++;
        }
        else if( set1[s1] < set2[s2])
        {
            s2++;
        }
        else
        {
            s1++;
        }
    }

    return result;
}



int main()
{
    vector<int> set1 = {1, 2, 4, 8, 16, 32};
    vector<int> set2 = {1, 2, 3, 4, 5, 6};

    auto set3 = set_intersection(set1, set2);
    for( auto a: set3 )
    {
        cout << a << endl;
    }
}