資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究判斷一個數組是否為另一個數組的子集 - 在 C++ 中添加了方法 3
在這個問題中，我們給定兩個整數陣列 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 是 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
另一種查詢解決方案的方法是首先對兩個陣列 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 的子集，是使用雜湊。我們將使用 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
解決此問題的另一種方法是使用集合資料結構。我們將使用 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[]
318 次檢視
