ソートされていない2つの配列から和集合と共通部分を求めるC++プログラム

はじめに

本記事では、ソートされていない2つの配列から和集合と共通部分（積集合）を求めるC++プログラムについて解説します。

和集合と共通部分とは

まず、2つの配列をそれぞれ「A」「B」と呼ぶことにします。

和集合（A ∪ B）とは、2つの配列に含まれるすべての要素を集めた配列のことです。ただし、重複する要素は1度しか現れないものとします。

共通部分（A ∩ B）とは、2つの配列のどちらにも存在する要素だけを集めた配列のことです。

アルゴリズムの流れ

和集合を求める手順

1. 別途配列を用意し、1つ目の配列の全要素をコピーします。
2. 2つ目の配列の要素を先頭から順に走査します。
3. その要素がすでに和集合の配列に存在するかどうかを確認し、存在しない場合のみ末尾に追加します。

共通部分を求める手順

1. 1つ目の配列の要素を1つずつ取り出します。
2. 同時に、その要素が2つ目の配列にも存在するかどうかを確認します。
3. 両方の配列に存在する場合は、共通部分の配列に追加します。

サンプルコード

#include <iostream>
using namespace std;
int main() {
    int len1 = 4, len2 = 3, flag1 = 0, flag2 = 0;
    int array1[len1] = {1,2,3,4}, array2[len2] = {5,3,4};
    int uni[len1+len2] = {1,2,3,4}, inter[len1];
    for(int k = 0; k < len2 ; k++) {
        flag1 = len1;
        for(int m = 0; m < len1; m++) {
            //与えられた配列間で重複する要素を除外する
            if(array2[k] == uni[m])
                break;
            else if(m == len1-1) {
                uni[flag1] = array2[k];
                flag1 = flag1+1;
            }
        }
    }
    for(int q = 0; q < len1; q++) {
        for(int w = 0; w < len2; w++) {
            //両方の配列に同じ要素が含まれているか確認する
            if(array1[q] == array2[w]) {
                inter[flag2] = array1[q];
                flag2 = flag2+1;
                break;
            }
        }
    }
    cout << "Union :" << endl;
    for(int u = 0; u < flag1; u++) {
        cout << uni[u] << " ";
    }
    cout << "\nIntersection :" << endl;
    for(int i = 0; i < flag2; i++) {
        cout << inter[i] << " ";
    }
    return 0;
}

実行結果

Union :
1 2 3 4
Intersection :
3 4

計算量に関する補足

この実装では、和集合・共通部分のいずれの処理も二重ループを使用しているため、時間計算量は O(n × m) となります。配列のサイズが大きくなると処理速度が低下するため、実務では std::unordered_set を活用することで、平均 O(n + m) まで高速化できる点も覚えておくとよいでしょう。