ค้นหาว่าอาร์เรย์เป็นชุดย่อยของอาร์เรย์อื่นหรือไม่ - เพิ่มวิธีที่ 3 ใน C++

ในปัญหานี้ เราจะได้รับจำนวนเต็มสองอาร์เรย์ arr1[] และ arr2[] ที่มีขนาด m และ n งานของเราคือ ค้นหาว่าอาร์เรย์นั้นเป็นชุดย่อยของอาร์เรย์อื่นหรือไม่ - เพิ่มวิธีที่ 3 .

ทั้งอาร์เรย์ arr1[] และ arr2[] ไม่เป็นระเบียบและมีองค์ประกอบที่แตกต่างกัน

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

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

แนวทางการแก้ปัญหา

เพื่อแก้ปัญหานี้ เราได้กล่าวถึงวิธีการหลายวิธีที่นี่ มาดูการทำงานของแต่ละคนด้วยโปรแกรมกันเลย

วิธีที่ 1

วิธีหนึ่งในการแก้ปัญหาคือการตรวจสอบชุดย่อยโดยตรง ทำได้โดยใช้การวนซ้ำที่ซ้อนกัน ด้านนอกสำหรับแต่ละองค์ประกอบของอาร์เรย์ arr2[] และภายใน สำหรับแต่ละองค์ประกอบของอาร์เรย์ arr1[] เราจะตรวจสอบว่าแต่ละองค์ประกอบของ arr2 มีอยู่ใน arr1 หรือไม่ ถ้ามันเป็นผลตอบแทน 1 ( arr2 คือ subarray ของ arr1) มิฉะนั้น คืนค่า 0 (arr2 ไม่ใช่ subarray ของ 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 ให้ทำการค้นหาแบบไบนารีเพื่อค้นหาองค์ประกอบของ arr2[] ใน arr1[] ตอนนี้ หากไม่พบองค์ประกอบใดๆ ให้คืนค่า 0 (arr2 ไม่ใช่อาร์เรย์ย่อยของ arr1) และหากองค์ประกอบทั้งหมดของ arr2 มีอยู่ใน arr1 ให้คืนค่า 1 (arr2 คือ subarrayof 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

อีกวิธีหนึ่งในการค้นหาวิธีแก้ปัญหาคือการเรียงลำดับทั้งอาร์เรย์ 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

อีกวิธีหนึ่งเพื่อตรวจสอบว่า arr2 เป็นเซตย่อยของ arr1 นั้นใช้ hashing อยู่หรือไม่ . เราจะสร้างตารางแฮชโดยใช้องค์ประกอบทั้งหมดของ 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

อีกวิธีหนึ่งในการแก้ปัญหาคือการใช้ 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[]