数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究检查数组元素重新排列后是否能放入另一个数组
从问题陈述中，我们可以理解到，给定两个数组，我们需要检查第一个数组是否可以放入第二个数组。
在现实世界中，有很多情况需要我们检查通过重新排列数组元素后，一个数组是否可以放入另一个数组。
出于各种原因，程序员可能需要重新排列数组的元素，以查看它们是否可以放入另一个数组。计算机编程中的内存管理就是一个这样的原因。当处理大量数据时，使用数组存储这些数据通常更有效；但是，由于内存限制，可能需要以特定方式排列数组以避免内存限制。
解释
让我们尝试解码这个问题。
假设您有两个数组：大小为 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 both arrays
sort(arr_1.begin(), arr_1.end());
sort(arr_2.begin(), arr_2.end());
// Check if arr_1 can fit into 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);
// Check whether B can fit into A
if (can_fit(A, B)) {
cout << "Array A can fit into array B by rearranging the elements." << endl;
} else {
cout << "Array A cannot fit into Array B by rearranging the elements." << endl;
}
return 0;
}
输出
Array A cannot fit into array B by rearranging the elements.
复杂度
时间复杂度：O(n log n)，因为这段代码首先对两个数组进行排序，并执行一次迭代。
空间复杂度：O(n)，因为我们在内存中存储了两个向量的元素。
结论
在本文中，我们试图解释检查一个数组是否可以放入另一个数组的方法。我希望这篇文章能帮助你更好地理解这个概念。
265 次浏览
