【C言語】2つの配列の積集合（交差）を求めるプログラムの作り方

積集合（交差）演算とは

積集合とは、2つの配列（集合）に共通して含まれる要素だけを集めたものです。

たとえば、次のような2つの配列があるとします。

• 配列1 = { 1, 2, 3, 4, 6 }
• 配列2 = { 1, 2, 5, 6, 7 }

両方の配列に存在するのは「1」「2」「6」の3つなので、積集合は次のようになります。

Array1 ^ Array2 = {1,2,3,4,6} ^ {1,2,5,6,7}
                 = {1,2,6}

積集合を求める基本ロジック

考え方はシンプルで、「配列1の各要素が配列2の中に存在するかどうかをすべて調べる」というものです。一致する要素が見つかるたびに、結果を格納する配列へ追加していきます。

k = 0;
for(i = 0; i < size1; i++){
    for(j = 0; j < size2; j++){
        if(a[i] == b[j]){
            intersection[k] = a[i];
            k++;
        }
    }
}

変数 k は、結果配列に格納された要素の個数を表します。この手法の計算量は O(n × m)（n、m はそれぞれの配列の要素数）です。

積集合を求めるCプログラム

以下が、2つの配列の積集合を求めるCプログラムの全体像です。同じ要素が複数回見つかるケースに備え、結果をソートした上で重複を削除しています。

#include<stdio.h>
int removerepeated(int size,int a[]);
void sort(int size,int a[]);
int main(){
    int i,size1,size2,size,j=0,k,intersectionsize;
    printf("配列1のサイズを入力してください\n");
    scanf("%d",&size1);
    printf("配列2のサイズを入力してください\n");
    scanf("%d",&size2);
    int a[size1],b[size2],uni[size1+size2];
    if(size1<size2){
        intersectionsize=size1;
    }else if(size1>size2){
        intersectionsize=size2;
    }else{
        intersectionsize=size1;
    }
    int intersection[intersectionsize];
    printf("配列1の要素を入力してください\n");
    for(i=0;i<size1;i++){
        scanf("%d",&a[i]);
    }
    printf("配列2の要素を入力してください\n");
    for(i=0;i<size2;i++){
        scanf("%d",&b[i]);
    }
    /* 積集合の計算 */
    k=0;
    for(i=0;i<size1;i++){
        for(j=0;j<size2;j++){
            if(a[i]==b[j]){
                intersection[k]=a[i];
                k++;
            }
        }
    }
    /* ソート */
    sort(k,intersection);
    /* 重複の削除 */
    size=removerepeated(k,intersection);
    printf("積集合後の配列\n");
    if(size>0){
        for(i=0;i<size;i++){
            printf("%d\n",intersection[i]);
        }
    }else{
        printf("共通する要素はありません\n");
    }
    return 0;
}
int removerepeated(int size,int a[]){
    int i,j,k;
    for(i=0;i<size;i++){
        for(j=i+1;j<size;){
            if(a[i]==a[j]){
                for(k=j;k<size;k++){
                    a[k]=a[k+1];
                }
                size--;
            }else{
                j++;
            }
        }
    }
    return(size);
}
void sort(int size,int a[]){
    int i,j,temp;
    for(i=0;i<size;i++){
        for(j=i+1;j<size;j++){
            if(a[i]>a[j]){
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
}

プログラムのポイント

• sort関数：単純な交換ソートで配列を昇順に並べ替えます。重複する要素を隣接させ、検出しやすくするための前処理です。
• removerepeated関数：ソート済みの配列から重複要素を削除し、新しい要素数を返します。
• 配列の宣言に可変長配列（VLA）を使用しているため、コンパイルにはC99以降に対応したコンパイラが必要です。

実行結果

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

配列1のサイズを入力してください
5
配列2のサイズを入力してください
2
配列1の要素を入力してください
4
5
6
7
8
配列2の要素を入力してください
4
1
積集合後の配列
4

この実行例では、配列1 = {4, 5, 6, 7, 8} と 配列2 = {4, 1} の共通要素である「4」のみが出力されています。共通要素がひとつも存在しない場合は「共通する要素はありません」と表示されます。

まとめ

2つの配列の積集合は、全要素同士を二重ループで比較するだけで求められます。計算量は O(n × m) ですが、データ量が少なければ十分実用的です。より大規模なデータを扱う場合は、あらかじめ両方の配列をソートして先頭から順に照合する方法や、ハッシュテーブルを活用することで高速化できます。