檢查一個數組是否可以透過重新排列數組中的元素來適應另一個數組

從問題描述中，我們可以理解到，給定兩個數組，我們需要檢查第一個數組是否能夠適應第二個數組。

在現實世界中，有許多情況我們需要檢查一個陣列是否可以透過重新排列數組中的元素來適應另一個數組。

由於各種原因，程式設計師可能需要重新排列數組的項，以查看它們是否適合另一個數組。電腦程式設計中的記憶體管理就是其中之一。在處理大量資料時，使用陣列來儲存資料通常更有效；但是，由於記憶體限制，可能需要按特定方式排列數組以避免記憶體限制。

Explanation

的翻譯為：

解釋

讓我們試著解碼這個問題。

假設你有兩個陣列：陣列A的大小為n，陣列B的大小為m，其中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，因為數組B中沒有元素1。

因此，在這種情況下，透過重新排列元素來檢查數組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)，因為我們在記憶體中儲存了兩個向量的元素。

結論

在本文中，我們嘗試解釋了檢查一個陣列是否可以適應另一個陣列的方法。希望這篇文章能幫助你更理解這個概念。

以上是檢查一個數組是否可以透過重新排列數組中的元素來適應另一個數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！