アレイが別のアレイのサブセットであるかどうかを確認する-C++でメソッド3を追加

---

この問題では、サイズmとnの整数arr1[]とarr2[]の2つの配列が与えられます。私たちのタスクは、配列が別の配列のサブセットであるかどうかを確認することです-方法3を追加しました 。

配列arr1[]とarr2[]はどちらも順序付けられておらず、異なる要素を持っています。

問題を理解するために例を見てみましょう

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

ソリューションアプローチ

この問題を解決するために、ここでは複数の方法について説明しました。それぞれのプログラムでの動作を見てみましょう。

方法1

この問題を解決する1つの方法は、サブセットを直接チェックすることです。これは、配列arr2 []の各要素に対して外側のループと、配列arr1[]の各要素に対して内側のループを使用して行われます。 arr2の各要素がarr1に存在するかどうかを確認します。それが1を返す場合（arr2はarr1のサブ配列）、そうでない場合は0を返します（arr2はarr1のサブ配列ではありません）。

例

ソリューションの動作を説明するプログラム

#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[]

のサブセットです

方法2

この問題を解決する別の方法は、arr2のすべての要素がarr1に存在するかどうかを確認することです。これを効果的に行うには、配列arr1 []を並べ替えてから、arr2の各要素に対して、バイナリ検索を実行してarr1[]内のarr2[]の要素を検索します。ここで、要素が見つからない場合は0を返し（arr2はarr1のサブ配列ではありません）、arr2のすべての要素がarr1に存在する場合は、1を返します（arr2はarr1のサブ配列です）。

例

ソリューションの動作を説明するプログラム

#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[]

のサブセットです

方法3

解決策を見つけるもう1つの方法は、最初に配列arr1[]とarr2[]の両方をソートすることです。次に、配列arr2 []のすべての要素について、それらがarr1[]に存在するかどうかを確認します。このために、両方の配列の要素のインデックスを使用する単純な方法があります。

例

ソリューションの動作を説明するプログラム

#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[]

のサブセットです

方法4

もう1つの方法は、arr2がarr1のサブセットであるかどうかを確認するために、ハッシュを使用することです。 。 arr1のすべての要素を使用してハッシュテーブルを作成し、ハッシュテーブルでarr2の要素を検索します。値が見つかった場合は1を返し（arr2はarr1のサブセットです）、そうでない場合は0を返します（arr2はarr1のサブセットではありません）。

例

ソリューションの動作を説明するプログラム

#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

この問題を解決するもう1つの方法は、 set data structureを使用することです。 。 arr1のすべての値を使用して新しいセットを作成し、その長さを確認します。次に、arr2のすべての値を挿入しようとします。追加すると長さが変更される場合、arr2はarr1のサブセットではありません。 arr2の要素を追加した後、長さに変化がない場合、arr2はarr1のサブセットです。

例

ソリューションの動作を説明するプログラム

#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[]

のサブセットです