判断一个数组是否是另一个数组的子集

2025年3月17日 | 阅读 12 分钟

提供了两个数组 arr1[0..m-1] 和 arr2[0..n-1]。确定 arr2[] 是否是 arr1[] 的子集。这两个数组都没有排序。可以假设两个数组中的每个元素都是唯一的。

示例

示例-1

输出

arr2[] is a subset of arr1[]

示例-2

输出

arr2[] is a subset of arr1[]

示例-3

输出

arr2[] is not a subset of arr1[]

检查一个数组是否是另一个数组的子集的简单方法

使用两个循环：外层循环单独选择 arr2[] 的每个成员。内层循环线性搜索外层循环选择的元素。如果找到所有元素，则返回 1；否则，返回 0。

上述策略的应用如下所示：

代码

// C++ program to find whether an array
// is subset of another array
#include <bits/stdc++.h>

/* Return 1 if arr2[] is a subset of
arr1[] */
bool isSubset(int arr1[], int arr2[], int m, int n)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (arr2[i] == arr1[j])
				break;
		}

		/* If the above inner loop was
		not broken at all then arr2[i]
		is not present in arr1[] */
		if (j == m)
			return 0;
	}

	/* If we reach here then all
	elements of arr2[] are present
	in arr1[] */
	return 1;
}

// Driver code
int main()
{
	int arr1[] = { 11, 1, 13, 21, 3, 7 };
	int arr2[] = { 11, 3, 7, 1 };

	int m = sizeof(arr1) / sizeof(arr1[0]);
	int n = sizeof(arr2) / sizeof(arr2[0]);

	if (isSubset(arr1, arr2, m, n))
		printf("arr2[] is subset of arr1[] ");
	else
		printf("arr2[] is not a subset of arr1[]");

	getchar();
	return 0;
}

输出

arr2[] is subset of arr1[]

时间复杂度： O(m*n)

空间复杂度： O(1)

使用排序和二分查找来确定一个数组是否是另一个数组的子集。

计划是对提供的数组 arr1[] 进行排序，然后对 arr2[] 中的每个成员在已排序的 arr1[] 中进行二分查找。如果找不到元素，则返回 0。如果所有元素都存在，则返回 1。

图解

给定数组 arr1[] = { 11, 1, 13, 21, 3, 7 } 和 arr2[] = { 11, 3, 7, 1 }。

步骤 1：我们将对数组 arr1[] 进行排序，得到 arr1[] = { 1, 3, 7, 11, 13, 21}。

步骤 2：我们将使用二分查找在 arr1[] 中搜索 arr2[] 中的每个元素。

arr2[] = { 11, 3, 7, 1 }，11 存在于 arr1[] = { 1, 3, 7, 11, 13, 21} 中
arr2[] = { 11, 3, 7, 1 }，11 存在于 arr1[] = { 1, 3, 7, 11, 13, 21} 中
arr2[] = { 11, 3, 7, 1 }，11 存在于 arr1[] = { 1, 3, 7, 11, 13, 21} 中
arr2[] = { 11, 3, 7, 1 }，11 存在于 arr1[] = { 1, 3, 7, 11, 13, 21} 中

由于找到了所有元素，我们可以得出 arr2[] 是 arr1[] 的子集。

算法

该算法很容易理解。

第一个数组 arr1 已排序。
在已排序的 arr1[] 中搜索 arr2[] 的元素。
如果遇到 arr2[] 中存在但 arr1[] 中不存在的特定值，则代码将终止；arr2[] 永远不可能是 arr1[] 的子集。
否则，arr1[] 是 arr2[] 的子集。

上述方法通过以下代码实现

代码

// C++ program to find whether an array
// is subset of another array
#include <bits/stdc++.h>
using namespace std;

/* Function prototypes */
void quickSort(int* arr, int si, int ei);
int binarySearch(int arr[], int low, int high, int x);

/* Return 1 if arr2[] is a subset of arr1[] */
bool isSubset(int arr1[], int arr2[], int m, int n)
{
	int i = 0;

	quickSort(arr1, 0, m - 1);
	for (i = 0; i < n; i++) {
		if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
			return 0;
	}

	/* If we reach here then all elements
	of arr2[] are present in arr1[] */
	return 1;
}

/* FOLLOWING FUNCTIONS ARE ONLY FOR
	SEARCHING AND SORTING PURPOSE */
/* Standard Binary Search function*/
int binarySearch(int arr[], int low, int high, int x)
{
	if (high >= low) {
		/*low + (high - low)/2;*/
		int mid = (low + high) / 2;

		/* Check if arr[mid] is the first
		occurrence of x. arr[mid] is first
		occurrence if x is one of the following
		is true:
		(i) mid == 0 and arr[mid] == x
		(ii) arr[mid-1] < x and arr[mid] == x */
		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;
}

void exchange(int* a, int* b)
{
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

int partition(int A[], int si, int ei)
{
	int x = A[ei];
	int i = (si - 1);
	int j;

	for (j = si; j <= ei - 1; j++) {
		if (A[j] <= x) {
			i++;
			exchange(&A[i], &A[j]);
		}
	}
	exchange(&A[i + 1], &A[ei]);
	return (i + 1);
}

/* Implementation of Quick Sort
A[] --> Array to be sorted
si --> Starting index
ei --> Ending index
*/
void quickSort(int A[], int si, int ei)
{
	int pi; /* Partitioning index */
	if (si < ei) {
		pi = partition(A, si, ei);
		quickSort(A, si, pi - 1);
		quickSort(A, pi + 1, ei);
	}
}

/*Driver code */
int main()
{
	int arr1[] = { 11, 1, 13, 21, 3, 7 };
	int arr2[] = { 11, 3, 7, 1 };

	int m = sizeof(arr1) / sizeof(arr1[0]);
	int n = sizeof(arr2) / sizeof(arr2[0]);

	if (isSubset(arr1, arr2, m, n))
		cout << "arr2[] is subset of arr1[] ";
	else
		cout << "arr2[] is not a subset of arr1[] ";

	return 0;
}

输出

arr2[] is subset of arr1[]

时间复杂度： O(nlog (m) + mLog (m))。排序需要 O(mLog(m))，在另一个数组中二分查找一个数组的每个元素需要 O(nlog(m))。代码中使用了快速排序，其最坏情况时间复杂度为 O. (m²)。

空间复杂度： O(n)

使用排序和合并来确定一个数组是否是另一个数组的子集。

计划是对两个数组进行排序，然后使用两个指针迭代地在第一个数组中搜索第二个数组的相同值。每次我们遇到相同的值时，我们都会增加指向两个数组的指针的值，如果我们遇到小于第二个数组的值，我们就会增加指向第一个数组的指针的值。如果值大于第二个数组，我们就会知道第二个数组不是第一个数组的子集。

图解

Find whether an array is subset of another array

算法

首先需要对两个数组进行排序。

设置一对指针 j 和 I，分别指向 arr1[] 和 arr2[]。
在这种情况下，如果 arr1[j] < arr2[i]，我们将 j 加 1。
如果 arr1[j] = arr2[i]，则将 j 和 I 都加 1。
如果 arr1[j] > arr2[i]，我们将停止，因为 arr2[] 不是 arr1[] 的子集。

上述策略的应用如下所示：

代码

// C++ program to find whether an array
// is subset of another array
#include <bits/stdc++.h>
using namespace std;

/* Return 1 if arr2[] is a subset of arr1[] */
bool isSubset(int arr1[], int arr2[], int m, int n)
{
	int i = 0, j = 0;

	if (m < n)
		return 0;

	// Sort both the arrays
	sort(arr1, arr1 + m);
	sort(arr2, arr2 + n);

	// Iterate till they do not exceed their sizes
	while (i < n && j < m) {
		// If the element is smaller then
		// Move ahead in the first array
		if (arr1[j] < arr2[i])
			j++;
		// If both are equal, then move
		// both of them forward
		else if (arr1[j] == arr2[i]) {
			j++;
			i++;
		}

		// If we do not have an element smaller
		// or equal to the second array then break
		else if (arr1[j] > arr2[i])
			return 0;
	}

	return (i < n) ? false : true;
}

// Driver Code
int main()
{
	int arr1[] = { 11, 1, 13, 21, 3, 7 };
	int arr2[] = { 11, 3, 7, 1 };

	int m = sizeof(arr1) / sizeof(arr1[0]);
	int n = sizeof(arr2) / sizeof(arr2[0]);

	if (isSubset(arr1, arr2, m, n))
		printf("arr2[] is subset of arr1[] ");
	else
		printf("arr2[] is not a subset of arr1[] ");

	return 0;
}

输出

arr2[] is subset of arr1[]

时间复杂度： O(mLog(m) + nLog(n))，这比方法 2 更好。

空间复杂度： O(1)

使用哈希来确定一个数组是否是另一个数组的子集。

概念是将第一个数组中的每个元素放入 HashSet，然后迭代第二个数组以查看元素是否存在，如果不存在，则确定第二个数组是否是第一个数组的子集。

图解

给定数组 arr1[] = { 11, 1, 13, 21, 3, 7 } 和 arr2[] = { 11, 3, 7, 1 }。

步骤 1：我们将 arr1[] 数组的元素存储在 HashSet 中

步骤 2：我们将使用二分查找在 arr1[] 中搜索 arr2[] 中的每个元素。

arr2[] = { 11, 3, 7, 1 }，11 存在于 HashSet = { 1, 3, 7, 11, 13, 21} 中
arr2[] = { 11, 3, 7, 1 }，3 存在于 HashSet = { 1, 3, 7, 11, 13, 21} 中
arr2[] = { 11, 3, 7, 1 }，7 存在于 HashSet = { 1, 3, 7, 11, 13, 21} 中
arr2[] = { 11, 3, 7, 1 }，1 存在于 HashSet = { 1, 3, 7, 11, 13, 21} 中

由于找到了所有元素，我们可以得出 arr2[] 是 arr1[] 的子集。

算法

该算法很容易理解。

在 HashSet 中保存第一个数组 arr1[]。
在 HashSet 中搜索 arr2[] 的元素。
如果遇到 arr2[] 中存在但 HashSet 中不存在的特定值，则代码将退出，因为 arr2[] 永远不可能是 arr1[] 的子集。
否则，arr1[] 是 arr2[] 的子集。

上述策略的应用如下所示：

代码

// C++ code to find whether an array is subset of
// another array
#include <bits/stdc++.h>
using namespace std;

/* Return true if arr2[] is a subset of arr1[] */
bool isSubset(int arr1[], int m, int arr2[], int n)
{

	// Using STL set for hashing
	set<int> hashset;

	// hset stores all the values of arr1
	for (int i = 0; i < m; i++) {
		hashset.insert(arr1[i]);
	}

	// loop to check if all elements of arr2 also
	// lies in arr1
	for (int i = 0; i < n; i++) {
		if (hashset.find(arr2[i]) == hashset.end())
			return false;
	}
	return true;
}

// Driver Code
int main()
{
	int arr1[] = { 11, 1, 13, 21, 3, 7 };
	int arr2[] = { 11, 3, 7, 1 };
	int m = sizeof(arr1) / sizeof(arr1[0]);
	int n = sizeof(arr2) / sizeof(arr2[0]);

	if (isSubset(arr1, m, arr2, n))
		cout << "arr2[] is subset of arr1[] "
			<< "\n";
	else
		cout << "arr2[] is not a subset of arr1[] "
			<< "\n";
	return 0;
}

输出

arr2[] is subset of arr1[]

时间复杂度： O(nLog(n))

空间复杂度： O(n)

使用 Set 确定一个数组是否是另一个数组的子集。

目标是将第一个和第二个数组中的每个成员都包含在 Set 中；如果 Set 的大小与 arr1[] 相同，则 arr2[] 是 arr1[] 的子集。因为 arr2[] 不包含任何新发现的元素，所以它是子集。

图解

给定数组 arr1[] = { 11, 1, 13, 21, 3, 7 } 和 arr2[] = { 11, 3, 7, 1 }。

步骤 1：我们将 arr1[] 和 arr2[] 数组的元素存储在 Set 中

最终的 Set = { 1, 3, 7, 11, 13, 21}

步骤 2：arr1[] 的大小 = 6，Set 的大小 = 6

因此，在 arr2[] 中没有找到新元素

由于找到了所有元素，我们可以得出 arr2[] 是 arr1[] 的子集。

算法

该算法很容易理解。

设置第一个数组 arr1[]。
应将第一个数组 arr1[] 保存在同一个 Set 中。
如果 arr1[] 的大小等于 Set 的大小，则 arr2[] 是 arr1[] 的子集。
否则，arr1[] 和 arr2[] 不是其子集。

代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
	// code
	int arr1[] = { 11, 1, 13, 21, 3, 7 };
	int arr2[] = { 11, 3, 7, 1 };
	int m = sizeof(arr1) / sizeof(arr1[0]);
	int n = sizeof(arr2) / sizeof(arr2[0]);
	unordered_set<int> s;
	for (int i = 0; i < m; i++) {
		s.insert(arr1[i]);
	}
	int p = s.size();
	for (int i = 0; i < n; i++) {
		s.insert(arr2[i]);
	}
	if (s.size() == p) {
		cout << "arr2[] is subset of arr1[] "
			<< "\n";
	}
	else {
		cout << "arr2[] is not subset of arr1[] "
			<< "\n";
	}
	return 0;
}

输出

arr2 [] is subset of arr1 []

给定数组 arr1 [] = { 11, 1, 13, 21, 3, 7 } 和 arr2 [] = { 11, 3, 7, 1 }。

步骤 1：我们将 arr1[] 数组的频率存储在频率数组中

频率数组将如下所示

步骤 2：我们将在频率数组中查找 arr2[] 元素。

arr2[] = { 11, 3, 7, 1 }，11 存在于频率数组中
arr2[] = { 11, 3, 7, 1 }，3 存在于频率数组中
arr2[] = { 11, 3, 7, 1 }，7 存在于频率数组中
arr2[] = { 11, 3, 7, 1 }，1 存在于频率数组中

由于找到了所有元素，我们可以得出 arr2[] 是 arr1[] 的子集。

算法

该算法很容易理解。

应使用频率数组来存储 arr1 [] 初始数组元素的频率。
在频率数组中搜索 arr2[] 迭代的元素。
如果值存在于频率数组中，则将频率值减一。
如果 arr2[] 中的任何元素的频率小于 1，我们将得出 arr2[] 不是 arr1[] 的子集。

上述策略的应用如下所示：

代码

// C++ program to find whether an array
// is subset of another array
#include <bits/stdc++.h>
using namespace std;
/* Return true if arr2[] is a subset of arr1[] */

bool isSubset(int arr1[], int m, int arr2[], int n)
{
	// Create a Frequency Table using STL
	map<int, int> frequency;

	// Increase the frequency of each element
	// in the frequency table.
	for (int i = 0; i < m; i++) {
		frequency[arr1[i]]++;
	}
	// Decrease the frequency if the
	// element was found in the frequency
	// table with the frequency more than 0.
	// else return 0 and if loop is
	// completed return 1.
	for (int i = 0; i < n; i++) {
		if (frequency[arr2[i]] > 0)
			frequency[arr2[i]]--;
		else {
			return false;
		}
	}
	return true;
}

// Driver Code
int main()
{
	int arr1[] = { 11, 1, 13, 21, 3, 7 };
	int arr2[] = { 11, 3, 7, 1 };
	int m = sizeof(arr1) / sizeof(arr1[0]);
	int n = sizeof(arr2) / sizeof(arr2[0]);

	if (isSubset(arr1, m, arr2, n))
		cout << "arr2[] is subset of arr1[] "
			<< "\n";
	else
		cout << "arr2[] is not a subset of arr1[] "
			<< "\n";
	return 0;
}

输出

arr2[] is subset of arr1[]

时间复杂度： O(m+n)，这比方法 1、2、3 更好。

空间复杂度： O(n)

请注意，方法 1、2、4 和 5 未处理 arr2[] 中存在重复元素的情况。例如，这些方法将输出 1，4，4，2，即使它不是 1，4，2 的子集。

下一主题按垂直顺序打印二叉树

判断一个数组是否是另一个数组的子集

示例

检查一个数组是否是另一个数组的子集的简单方法

代码

使用排序和二分查找来确定一个数组是否是另一个数组的子集。

图解

使用排序和合并来确定一个数组是否是另一个数组的子集。

图解

使用哈希来确定一个数组是否是另一个数组的子集。

图解

使用 Set 确定一个数组是否是另一个数组的子集。

图解

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

判断一个数组是否是另一个数组的子集

示例

检查一个数组是否是另一个数组的子集的简单方法

代码

使用排序和二分查找来确定一个数组是否是另一个数组的子集。

图解

使用排序和合并来确定一个数组是否是另一个数组的子集。

图解

使用哈希来确定一个数组是否是另一个数组的子集。

图解

使用 Set 确定一个数组是否是另一个数组的子集。

图解

相关帖子

经过恰好 K 步到达某个位置的方法数

根据军衔查找士兵完成的任务

DS 中的表达式树

根据给定的层序遍历构建 BST

查找给定范围内替换子数组以获得最大和

与给定数字最接近的三元组和

计算可被 k 整除的数组对

Kahn 算法 vs DFS 方法：比较分析

数据结构中栈的表示

查找和为零的最大子数组

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器