Vérifiez si un tableau peut s'insérer dans un autre tableau en réorganisant les éléments du tableau

D'après la description du problème, nous pouvons comprendre qu'étant donné deux tableaux, nous devons vérifier si le premier tableau peut s'insérer dans le deuxième tableau.

Dans le monde réel, il existe de nombreuses situations dans lesquelles nous devons vérifier si un tableau peut s'insérer dans un autre tableau en réorganisant les éléments du tableau.

Pour diverses raisons, un programmeur peut avoir besoin de réorganiser les éléments d'un tableau pour voir s'ils correspondent à un autre tableau. La gestion de la mémoire dans la programmation informatique en fait partie. Lorsque vous travaillez avec de grandes quantités de données, il est souvent plus efficace d'utiliser des tableaux pour stocker les données. Cependant, en raison des limitations de mémoire, les tableaux peuvent devoir être disposés d'une manière spécifique pour éviter les limitations de mémoire.

Explication

se traduit par :

Explication

Essayons de décoder cette question.

Supposons que vous ayez deux tableaux : le tableau A a une taille n et le tableau B a une taille m, où m est supérieur ou égal à n. La tâche consiste à vérifier s'il est possible de réorganiser les éléments du tableau A de telle sorte que le tableau A puisse être complètement contenu dans le tableau B.

En d'autres termes, chaque élément du tableau A doit être présent dans le tableau B et dans le même ordre que dans le tableau A. Cependant, il peut y avoir des éléments supplémentaires dans le tableau B qui ne sont pas présents dans le tableau A.

Par exemple, supposons que le tableau A contienne des éléments [3,2,1] et que le tableau B contienne des éléments [2, 1, 3, 4, 5]. Nous pouvons réorganiser les éléments du tableau A pour obtenir [3, 2, 1], qui peut alors être complètement contenu dans le tableau B comme indiqué ci-dessous −

D'un autre côté, si le tableau A contient des éléments [1, 2, 3] et que le tableau B contient des éléments [2, 3, 4, 5], nous ne pouvons pas réorganiser les éléments du tableau A pour qu'ils s'intègrent complètement dans le tableau B car dans le tableau B Il n’y a pas d’élément 1.

Donc, dans ce cas, la fonction qui vérifie si le tableau A peut s'insérer dans le tableau B en réorganisant les éléments renverra False.

Méthode

Décodeons l'intégralité du programme dans un algorithme étape par étape.

• Triez ces deux tableaux par ordre croissant.

• Compare les éléments de deux tableaux, en commençant par la première entrée de chaque tableau.

• Si l'élément du plus petit tableau est inférieur ou égal à l'élément correspondant du plus grand tableau, continuez à passer à l'élément suivant dans les deux tableaux.

• Si les éléments du plus petit tableau sont plus grands que les éléments correspondants du plus grand tableau, renvoyez "false" car le plus petit tableau ne peut pas tenir dans le plus grand tableau.

• Renvoie "true" si tous les éléments du plus petit tableau sont inférieurs ou égaux aux éléments correspondants du plus grand tableau, car le plus petit tableau peut s'insérer dans le plus grand tableau.

Remarque− En raison de l'étape de tri, la complexité de cet algorithme est O(n log n), où n est la taille du tableau.

Exemple

Implémentation du code C++ : vérifiez si un tableau peut s'insérer dans un autre tableau en réorganisant les éléments du tableau

#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;
}

Sortie

Array A cannot fit into array B by rearranging the elements.

Complexité

Complexité temporelle : O(n log n), car dans ce code, nous trions d'abord les deux tableaux puis effectuons une itération.

Complexité spatiale : O(n) car nous stockons les éléments de deux vecteurs en mémoire.

Conclusion

Dans cet article, nous avons essayé d'expliquer la méthode pour vérifier si un tableau peut s'insérer dans un autre tableau. J'espère que cet article vous aidera à mieux comprendre ce concept.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!