積集合(共通部分)を求める

広告

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

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

何も考えずにやると二重ループの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;
    }
}

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)