C++で2つのソート済み配列の相対補集合を求める方法

C++で2つのソート済み配列の相対補集合を求める方法

2つのソート済み配列 arr1 と arr2 があり、それぞれのサイズを m、n とします。ここで求めたいのは、この2つの配列の「相対補集合（相対的な差）」です。つまり、arr1 には存在するものの、arr2 には存在しないすべての要素を見つけるということです。

例えば、配列が次のような場合を考えてみましょう。

• A = [3, 6, 10, 12, 15]
• B = [1, 3, 5, 10, 16]

この場合、A には存在するが B には存在しない要素は 6、12、15 なので、結果は [6, 12, 15] となります。

解決アプローチ：set_difference 関数を使う

この問題は本質的に「集合の差（集合差演算）」と同じです。そのため、C++ の標準ライブラリ ヘッダーに用意されている set_difference 関数を使うことで、簡単に解決できます。

set_difference 関数は、第1のソート済み範囲には含まれるが、第2のソート済み範囲には含まれない要素だけを出力イテレータへ書き込みます。戻り値としては、結果の末尾を指すイテレータが返されるため、これを使って実際に書き込まれた要素の数を知ることができます。

サンプルコード

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main() {
   int first[] = {3, 6, 10, 12, 15};
   int second[] = {1, 3, 5, 10, 16};
   int n = sizeof(first) / sizeof(first[0]);
   vector<int> temp(5);
   vector<int>::iterator it, ls;

   sort(first, first + 5);
   sort(second, second + 5);

   cout << "First array :";
   for (int i = 0; i < n; i++)
      cout << " " << first[i];
   cout << endl;

   cout << "Second array :";
   for (int i = 0; i < n; i++)
      cout << " " << second[i];
   cout << endl;

   ls = set_difference(first, first + 5, second, second + 5, temp.begin());

   cout << "The result of relative complement ";
   for (it = temp.begin(); it < ls; ++it)
      cout << " " << *it;
   cout << endl;
}

実行結果

First array : 3 6 10 12 15
Second array : 1 3 5 10 16
The result of relative complement 6 12 15

コードのポイント

• 事前のソートが必須： set_difference は入力範囲がソート済みであることを前提としているため、あらかじめ sort 関数で両方の配列をソートしておく必要があります。
• 結果の格納先： 結果を受け取るための vector を用意し、temp.begin() を出力イテレータとして渡しています。
• 戻り値の活用： set_difference の戻り値（ls）は結果の末尾の次を指すため、これを使えば書き込まれた要素だけを効率よく出力できます。
• 計算量： このアルゴリズムの計算量は O(m + n) で、2つの配列をそれぞれ1回ずつ走査するだけで済むため、非常に効率的です。

このように、set_difference を使えば、2つのソート済み配列の相対補集合を短いコードで高速に求めることができます。なお、重複要素が存在する場合、set_difference は「第1の配列における出現回数から第2の配列における出現回数を引いた回数」だけ要素を出力する点にも注意してください。