【C++】ある配列が別の配列の部分集合（サブセット）かどうかを判定する5つの方法

問題の概要

この問題では、サイズ m の整数型配列 arr1[] と、サイズ n の整数型配列 arr2[] が与えられます。求めたいのは、「arr2 が arr1 の部分集合（サブセット）であるかどうか」の判定です。

なお、両方の配列は順序がバラバラで、要素に重複はないものとします。

入力例

Input : arr1[] = {5, 2, 1, 6, 8, 10}, arr2[] = {6, 2, 1}
Output : arr2 is a subset of arr1.

解決アプローチ

この問題は複数の手法で解くことができます。ここでは代表的な5つの方法を、それぞれの仕組みと実装例とあわせて解説します。

方法1：ネストしたループによる線形探索

最もシンプルな方法は、直接すべての要素を照合することです。外側のループで arr2[] の各要素を取り出し、内側のループで arr1[] の全要素と比較します。arr2 の全要素が arr1 に存在すれば true（部分集合）、1つでも存在しなければ false（部分集合ではない）を返します。

実装例

#include <iostream>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
    int j = 0;
    for (int i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (arr2[i] == arr1[j])
                break;
        }
        if (j == m)
            return false;
    }
    return true;
}
int main(){
    int arr1[] = {5, 2, 1, 6, 8, 10};
    int arr2[] = {6, 2, 1};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
    return 0;
}

出力

arr2[] is subset of arr1[]

この方法は直感的ですが、計算量は O(m×n) となるため、配列が大きくなると非効率になります。

方法2：ソート＋二分探索

次の方法では、まず arr1[] をソートしておき、arr2[] の各要素について二分探索で arr1[] 内に存在するかを確認します。どれか1つでも見つからなければ false を返し、すべて見つかれば true を返します。

実装例

#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int low, int high, int x){
    if (high >= low){
        int mid = (low + high) / 2;
        if ((mid == 0 || x > arr[mid - 1]) && (arr[mid] == x))
            return mid;
        else if (x > arr[mid])
            return binarySearch(arr, (mid + 1), high, x);
        else
            return binarySearch(arr, low, (mid - 1), x);
    }
    return -1;
}
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
    int i = 0;
    sort(arr1, arr1 + m);
    for (i = 0; i < n; i++) {
        if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
            return 0;
    }
    return 1;
}
int main(){
    int arr1[] = {5, 2, 1, 6, 8, 10};
    int arr2[] = {6, 2, 1};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
    return 0;
}

出力

arr2[] is subset of arr1[]

ソートに O(m log m)、要素ごとの二分探索に O(log m) かかるため、全体の計算量は O(m log m + n log m) となり、方法1より高速です。

方法3：両方の配列をソートしてマージのように比較

もうひとつの効率的な方法が、arr1[] と arr2[] の両方をソートしてから、インデックスを進めながら要素を順番に比較する手法です。これは本記事で追加する「方法3」にあたります。

まず、m < n の場合は arr2 の方が大きいため時点で false を返します。その後、両配列をソートし、2つのポインタ i・j を使って次のように判定します。

• arr1[j] < arr2[i] の場合 → j を進める
• arr1[j] == arr2[i] の場合 → i と j を両方進める
• arr1[j] > arr2[i] の場合 → arr2[i] が arr1 に存在しないことが確定するため false を返す

実装例

#include <bits/stdc++.h>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
    int i = 0, j = 0;
    if (m < n)
        return 0;
    sort(arr1, arr1 + m);
    sort(arr2, arr2 + n);
    while (i < n && j < m){
        if (arr1[j] < arr2[i])
            j++;
        else if (arr1[j] == arr2[i]){
            j++;
            i++;
        }
        else if (arr1[j] > arr2[i])
            return 0;
    }
    return (i < n) ? false : true;
}
int main()
{
    int arr1[] = {5, 2, 1, 6, 8, 10};
    int arr2[] = {6, 2, 1};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
    return 0;
}

出力

arr2[] is subset of arr1[]

計算量はソートが支配的で、O(m log m + n log n) です。ソート後に一度の走査で済むため、二分探索を繰り返す方法2よりも実行速度が安定しやすいのが特徴です。

方法4：ハッシュ（set）を使う方法

4つ目の方法はハッシュを利用するものです。arr1 の全要素からハッシュテーブル（set）を作成し、arr2 の各要素がそのテーブルに存在するかを検索します。すべて見つかれば true、1つでも見つからなければ false を返します。

実装例

#include <bits/stdc++.h>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
    set<int> arr1Hash;
    for (int i = 0; i < m; i++)
        arr1Hash.insert(arr1[i]);
    for (int i = 0; i < n; i++) {
        if (arr1Hash.find(arr2[i]) == arr1Hash.end())
            return false;
    }
    return true;
}
int main(){
    int arr1[] = {5, 2, 1, 6, 8, 10};
    int arr2[] = {6, 2, 1};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
    return 0;
}

出力

arr2[] is subset of arr1[]

方法5：set データ構造のサイズ変化を利用する方法

最後の方法は、set データ構造の性質（重複した要素を持てない）を利用したものです。手順は以下の通りです。

1. arr1 の全要素を挿入した set を作成し、そのサイズを記録する。
2. 続けて arr2 の全要素を同じ set に挿入する。
3. 挿入後に set のサイズが変わっていなければ、arr2 の全要素は arr1 に含まれていたことになるため true。
4. サイズが増えていれば、arr1 に存在しない要素があったということなので false。

実装例

#include <bits/stdc++.h>
using namespace std;
bool isSubsetArray(int arr1[], int arr2[], int m, int n){
    unordered_set<int> arrSet;
    for (int i = 0; i < m; i++) {
        arrSet.insert(arr1[i]);
    }
    int setSize = arrSet.size();
    for (int i = 0; i < n; i++) {
        arrSet.insert(arr2[i]);
    }
    if (arrSet.size() == setSize) {
        return true;
    }
    else {
        return false;
    }
}
int main(){
    int arr1[] = {5, 2, 1, 6, 8, 10};
    int arr2[] = {6, 2, 1};
    int m = sizeof(arr1) / sizeof(arr1[0]);
    int n = sizeof(arr2) / sizeof(arr2[0]);
    isSubsetArray(arr1, arr2, m, n)? cout<<"arr2[] is subset of arr1[] ": cout<<"arr2[] is not a subset of arr1[]";
    return 0;
}

出力

arr2[] is subset of arr1[]

まとめ

配列の部分集合判定には、単純な二重ループから二分探索、ソート後のマージ的比較、ハッシュ、set の活用まで、さまざまなアプローチがあります。

データサイズや重複の有無、実行環境に応じて最適な手法を選択しましょう。