数据结构
网络
关系数据库管理系统
操作系统
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 次查看
