2つのソート済み配列から共通しない要素を出力するC言語プログラム

2つのソート済み配列が与えられたとき、両方の配列に共通して含まれる要素を取り除き、どちらか一方にのみ存在する要素（共通しない要素）だけを出力する方法を解説します。配列がすでにソートされていることを利用すると、追加のメモリを使わずに線形時間で効率よく処理できます。

入力例 : array1[]= {1, 4, 6, 9, 12}
         array2[]= {2, 4, 7, 8, 9, 10}
出力例 : 1 2 6 7 8 10 12

アルゴリズム

基本的な考え方は、マージソートのマージ処理と同じです。両方の配列を先頭から順番に比較し、値が小さいほうの要素を出力してインデックスを進めます。両者の値が一致した場合は共通要素なので出力せず、両方のインデックスを同時に進めます。どちらか一方の配列を読み終えたら、残った側の要素を末尾まで出力します。

START
Step 1 -> int型の2つの配列 array1 と array2 を用意し、変数 n1、n2、i を 0、j を 0 で初期化する
Step 2 -> sizeof(array1)/sizeof(array1[0]) により array1 の要素数を求める
Step 3 -> sizeof(array2)/sizeof(array2[0]) により array2 の要素数を求める
Step 4 -> i<n1 かつ j<n2 の間、以下を繰り返す
    IF array1[i]<array2[j]
        array1[i] を出力し、i++ する
    End IF
    ELSE IF array1[i]>array2[j]
        array2[j] を出力し、j++ する
    End ELSE IF
    ELSE
        値が等しい場合は共通要素のため出力せず、i++ と j++ のみ行う
    End ELSE
Step 5 -> While ループを終了する
Step 6 -> i<n1 かつ array1[i]!=array2[j] の間、array1[i] を出力し i++ する
Step 7 -> While ループを終了する
Step 8 -> j<n2 かつ array2[j]!=array1[i] の間、array2[j] を出力し j++ する
Step 9 -> While ループを終了する
STOP

C言語による実装例

以下は、上記のアルゴリズムをC言語で実装したサンプルコードです。

#include <stdio.h>
int main(int argc, char const *argv[]) {
    int array1[]= {1, 4, 6, 9, 12};
    int array2[]= {2, 4, 7, 8, 9, 10};
    int n1, n2, i=0, j=0;
    n1 = sizeof(array1)/sizeof(array1[0]); // array1 の要素数を計算
    n2 = sizeof(array2)/sizeof(array2[0]); // array2 の要素数を計算
    while(i < n1 && j < n2) {
        if(array1[i] < array2[j]) // array1 の要素のほうが小さい場合
            printf("%d\n", array1[i++]);
        else if (array1[i] > array2[j]) // array2 の要素のほうが小さい場合
            printf("%d\n", array2[j++]);
        else { // 等しい場合は共通要素なので両方のインデックスを進める
            i++;
            j++;
        }
    }
    while(i < n1 && array1[i]!=array2[j]) // array1 の残りの要素を出力
        printf("%d\n", array1[i++]);
    while(j < n2 && array2[j]!=array1[i]) // array2 の残りの要素を出力
        printf("%d\n", array2[j++]);
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。共通要素である 4 と 9 が出力されておらず、それ以外の要素が昇順に表示されていることが確認できます。

1
2
6
7
8
10
12

計算量とポイント

この手法では、各配列の要素をそれぞれ一度ずつ走査するだけでよいため、時間計算量は O(n1 + n2) となり、非常に効率的です。また、結果を保存するための追加の配列が不要で、その場で出力できる点もメリットです。なお、この方法が正しく動作するためには、両方の配列があらかじめ昇順にソートされていることが前提となります。ソートされていない配列に対しては、あらかじめ qsort 関数などで並べ替えてから適用してください。