通过重新排列数组中的元素来检查一个数组是否适合另一个数组
从问题陈述中，我们可以理解，给定两个数组，我们必须检查第一个数组是否适合第二个数组。
在现实世界中，有很多情况下我们需要通过重新排列数组中的元素来检查一个数组是否适合另一个数组。
出于各种原因，程序员可能需要重新排序数组的项目以查看它们是否可以放入另一个数组。计算机编程中的内存管理就是这样一个原因。处理大量数据时，使用数组来存储数据通常更有效；但是，由于内存限制，可能需要以特定方式排列数组以避免内存限制。
解释
让我们尝试解码这个问题。
假设您有两个数组:大小为 n 的数组 A 和大小为 m 的数组 B，其中 m 大于或等于 n。任务是检查是否可以按任何顺序重新排列数组 A 的元素，以使数组 A 可以完全包含在数组 B 中。
换句话说，数组 A 的每个元素都必须存在于数组 B 中，并且顺序与它们在数组 A 中出现的顺序相同。但是，数组 B 中可以有数组 A 中不存在的其他元素。
例如，假设数组 A 包含元素 [3,2,1]，数组 B 包含元素 [2, 1, 3, 4, 5]。我们可以重新排列数组 A 中的元素以获得 [3, 2, 1]，然后可以完全包含在数组 B 中，如下所示 -
另一方面，如果数组 A 包含元素 [1, 2, 3] 且数组 B 包含元素 [2, 3, 4, 5]，则我们无法重新排列数组 A 中的元素以完全适合数组 B，因为元素 1 不存在于数组 B 中。
因此，在这种情况下，通过重新排列元素来检查数组 A 是否适合数组 B 的函数将返回 False。
方法
让我们将整个程序解码为分步算法。
按升序对两个数组进行排序。
比较两个数组的元素，从每个数组中的第一个条目开始数组。
如果较小数组的元素小于或等于较大数组中的等效元素，则转到两个数组中的下一个元素。
如果较小数组的元素大于较大数组中的等效元素，则返回"false"，因为较小数组无法放入较大数组中。
如果较小数组的所有项目都小于或等于较大数组中的相应元素，则返回"true"，因为较小数组可以放入较大数组中。
注意 - 由于排序步骤，此算法的复杂度为 O(n log n)，其中 n 是数组的大小。
示例
C++ 代码实现:通过重新排列数组中的元素来检查数组是否可以放入另一个数组
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool can_fit(vector<int>& arr_1, vector<int>& arr_2) {
//base case
if(arr_1.size() > arr_2.size())
return false;
// 对两个数组进行排序
sort(arr_1.begin(), arr_1.end());
sort(arr_2.begin(), arr_2.end());
// 检查 arr_1 是否可以放入 arr_2
int i = 0, j = 0;
while (i < arr_1.size() && j < arr_2.size()) {
if (arr_1[i] <= arr_2[j]) {
i++;
j++;
} else {
return false;
}
}
return true;
}
int main() {
vector<int> A, B;
A.push_back(2);
A.push_back(5);
A.push_back(7);
A.push_back(9);
A.push_back(10);
B.push_back(1);
B.push_back(3);
B.push_back(5);
B.push_back(7);
B.push_back(9);
B.push_back(9);
B.push_back(10);
// 检查 B 是否可以适合 A
if (can_fit(A, B)) {
cout << "通过重新排列元素，数组 A 可以放入数组 B 中。" << endl;
} else {
cout << "通过重新排列元素，数组 A 无法容纳数组 B。" << endl;
}
return 0;
}
输出
通过重新排列元素，数组 A 无法容纳数组 B。
复杂性
时间复杂度:O(n log n)，因为在此代码中，我们首先对两个数组进行排序，然后执行一次迭代。
空间复杂度:O(n)，因为我们将两个向量的元素存储在内存中。
结论
在本文中，我们尝试解释检查数组是否适合另一个数组的方法。我希望本文能帮助您更好地学习这个概念。
