Tìm xem một mảng có phải là tập hợp con của một mảng khác hay không - Đã thêm Phương pháp 3 trong C ++

Trong bài toán này, chúng ta được cung cấp hai mảng số nguyên arr1 [] và arr2 [] có kích thước m và n. Nhiệm vụ của chúng ta là tìm xem một mảng có phải là một tập hợp con của một mảng khác hay không - Phương pháp đã thêm 3 .

Cả hai mảng arr1 [] và arr2 [] đều không có thứ tự và có các phần tử riêng biệt.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề này, chúng tôi đã thảo luận nhiều phương pháp ở đây. Hãy xem hoạt động của từng người trong số họ với một chương trình.

Phương pháp 1

Một phương pháp để giải quyết vấn đề là kiểm tra trực tiếp các tập con. Điều này được thực hiện bằng cách sử dụng các vòng lặp lồng nhau, bên ngoài cho mỗi phần tử của mảng arr2 [] và bên trong, cho mỗi phần tử của mảng arr1 []. Chúng tôi sẽ kiểm tra xem từng phần tử của arr2 có trong arr1 hay không, nếu nó trả về 1 (arr2 là mảng con của arr1) nếu không thì trả về 0 (arr2 không phải là mảng con của arr1).

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

arr2[] is subset of arr1[]

Phương pháp 2

Một phương pháp khác để giải quyết vấn đề là kiểm tra xem tất cả các phần tử của arr2 có trong arr1 hay không. Để làm điều này một cách hiệu quả, chúng ta sẽ sắp xếp mảng arr1 [] và sau đó đối với mỗi phần tử của arr2, thực hiện tìm kiếm nhị phân để tìm kiếm các phần tử của arr2 [] trong arr1 []. Bây giờ, nếu không tìm thấy bất kỳ phần tử nào, hãy trả về 0 (arr2 không phải là một mảng con của arr1) và nếu tất cả các phần tử của arr2 đều có trong arr1, hãy trả về 1 (arr2 là một mảng con của arr1).

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

arr2[] is subset of arr1[]

Phương pháp 3

Một phương pháp nữa để tìm lời giải là trước tiên hãy sắp xếp cả hai mảng arr1 [] và arr2 []. Sau đó, đối với tất cả các phần tử của mảng arr2 [], hãy kiểm tra xem chúng có trong arr1 [] hay không. Đối với điều này, chúng tôi có một phương thức thẳng sử dụng chỉ mục của các phần tử trong cả hai mảng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

arr2[] is subset of arr1[]

Phương pháp 4

Một phương pháp khác, để kiểm tra xem arr2 có phải là tập con của arr1 hay không đang sử dụng băm . Chúng tôi sẽ tạo một bảng băm bằng cách sử dụng tất cả các phần tử của arr1 và sau đó tìm kiếm các phần tử của arr2 trong bảng băm. Nếu các giá trị được tìm thấy thì trả về 1 (arr2 là tập con của arr1) còn lại thì trả về 0 (arr2 không phải là tập con của arr1).

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

arr2[] is subset of arr1[]

Phương pháp 5

Một phương pháp khác để giải quyết vấn đề là sử dụng cấu trúc thiết lập dữ liệu . Chúng tôi sẽ tạo một tập hợp mới với tất cả các giá trị của arr1 và kiểm tra độ dài của nó. Sau đó, chúng tôi sẽ cố gắng chèn tất cả các giá trị của arr2, nếu thêm thay đổi độ dài thì arr2 không phải là một tập con của arr1. Nếu không có thay đổi về độ dài xảy ra sau khi thêm các phần tử của arr2 thì arr2 là một tập con của arr1.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

arr2[] is subset of arr1[]