資料結構
網路
關係資料庫管理系統 (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 次瀏覽
