C++でソートされていない2つの配列の和集合（Union）と積集合（Intersection）を求める方法

このチュートリアルでは、ソートされていない2つの配列から和集合（Union）と積集合（Intersection）を求めるプログラムの書き方を解説します。まずは、具体的な入力と出力の例を見てみましょう。

入力

arr_one = [1, 2, 3, 4, 5]
arr_two = [3, 4, 5, 6, 7]

出力

union: 1 2 3 4 5 6 7
intersection: 3 4 5

それでは、問題を解くための手順を順番に確認していきましょう。

和集合（Union）を求める手順

• 2つの配列を任意の値で初期化します。

• 結果を格納するための空の配列 union_result を用意します。

• 1つ目の配列を走査し、すべての要素を union_result に追加します。

• 2つ目の配列を走査し、union_result にまだ存在しない要素だけを追加します。これにより重複を防ぐことができます。

• union_result の内容を出力します。

積集合（Intersection）を求める手順

• 2つの配列を任意の値で初期化します。

• 結果を格納するための空の配列 intersection_result を用意します。

• 1つ目の配列を走査し、2つ目の配列にも存在する要素だけを intersection_result に追加します。

• intersection_result の内容を出力します。

サンプルコード

以下が実際のC++コードです。

#include <bits/stdc++.h>
using namespace std;

// 配列の中に指定した要素が存在するかを判定する関数
bool isElementPresentInArray(int arr[], int arr_length, int element) {
    for (int i = 0; i < arr_length; ++i) {
        if (arr[i] == element) {
            return true;
        }
    }
    return false;
}

// 2つの配列の和集合と積集合を求めて表示する関数
void findUnionAndIntersection(int arr_one[], int arr_one_length, int arr_two[], int arr_two_length) {
    // ---- 和集合（Union）----
    int union_result[arr_one_length + arr_two_length] = {};

    // 1つ目の配列の全要素をコピー
    for (int i = 0; i < arr_one_length; ++i) {
        union_result[i] = arr_one[i];
    }

    int union_index = arr_one_length;

    // 2つ目の配列のうち、まだ結果に含まれていない要素だけを追加
    for (int i = 0; i < arr_two_length; ++i) {
        if (!isElementPresentInArray(union_result, union_index, arr_two[i])) {
            union_result[union_index++] = arr_two[i];
        }
    }

    cout << "Union: ";
    for (int i = 0; i < union_index; ++i) {
        cout << union_result[i] << " ";
    }
    cout << endl;

    // ---- 積集合（Intersection）----
    int intersection_result[arr_one_length + arr_two_length] = {};
    int intersection_index = 0;

    // 1つ目の配列の要素が2つ目の配列にも存在する場合のみ追加
    for (int i = 0; i < arr_one_length; ++i) {
        if (isElementPresentInArray(arr_two, arr_two_length, arr_one[i])) {
            intersection_result[intersection_index++] = arr_one[i];
        }
    }

    cout << "Intersection: ";
    for (int i = 0; i < intersection_index; ++i) {
        cout << intersection_result[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr_one[] = {1, 2, 3, 4, 5};
    int arr_two[] = {3, 4, 5, 6, 7};

    findUnionAndIntersection(arr_one, 5, arr_two, 5);

    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。

Union: 1 2 3 4 5 6 7
Intersection: 3 4 5

補足：計算量と注意点

このアルゴリズムでは、要素の存在確認を線形探索で行っているため、計算量は O(n × m) となります。配列のサイズが大きくなると処理時間が増加するため、std::set や std::unordered_set を活用すると、より効率的に実装できます。また、コード中の可変長配列（VLA）はGCCなどのコンパイラ拡張機能であり、標準C++では動作が保証されていません。移植性を重視する場合は、std::vector の使用を検討してください。

まとめ

今回は、ソートされていない2つの配列に対して、和集合と積集合を求める基本的な方法を学びました。まずはシンプルな線形探索による実装の仕組みをしっかり理解し、その後、より効率的なデータ構造への置き換えにも挑戦してみてください。このチュートリアルについて質問がある場合は、コメント欄でお気軽にお尋ねください。