Überprüfen Sie, ob ein Array in ein anderes Array passt, indem Sie die Elemente im Array neu anordnen

Aus der Problembeschreibung können wir verstehen, dass wir bei zwei gegebenen Arrays prüfen müssen, ob das erste Array in das zweite Array passen kann.

In der realen Welt gibt es viele Situationen, in denen wir prüfen müssen, ob ein Array in ein anderes Array passt, indem wir die Elemente im Array neu anordnen.

Aus verschiedenen Gründen muss ein Programmierer möglicherweise die Elemente eines Arrays neu anordnen, um zu sehen, ob sie in ein anderes Array passen. Eine davon ist die Speicherverwaltung in der Computerprogrammierung. Bei der Arbeit mit großen Datenmengen ist es oft effizienter, Arrays zum Speichern von Daten zu verwenden. Aufgrund von Speicherbeschränkungen müssen Arrays jedoch möglicherweise auf eine bestimmte Weise angeordnet werden, um Speicherbeschränkungen zu vermeiden.

Erklärung

wird übersetzt als:

Erklärung

Versuchen wir, diese Frage zu entschlüsseln.

Angenommen, Sie haben zwei Arrays: Array A hat die Größe n und Array B hat die Größe m, wobei m größer oder gleich n ist. Die Aufgabe besteht darin, zu prüfen, ob es möglich ist, die Elemente von Array A so umzuordnen, dass Array A vollständig in Array B enthalten sein kann.

Mit anderen Worten: Jedes Element von Array A muss in Array B und in derselben Reihenfolge wie in Array A vorhanden sein. Allerdings kann es in Array B zusätzliche Elemente geben, die in Array A nicht vorhanden sind.

Angenommen, Array A enthält die Elemente [3,2,1] und Array B enthält die Elemente [2, 1, 3, 4, 5]. Wir können die Elemente von Array A neu anordnen, um [3, 2, 1] zu erhalten, die dann vollständig in Array B enthalten sein können, wie unten gezeigt −

Wenn andererseits Array A die Elemente [1, 2, 3] und Array B die Elemente [2, 3, 4, 5] enthält, können wir die Elemente von Array A nicht so neu anordnen, dass sie vollständig in Array B passen, da in Array B Es gibt kein Element 1.

In diesem Fall gibt die Funktion, die prüft, ob Array A durch Neuanordnen der Elemente in Array B passen kann, False zurück.

Methode

Lassen Sie uns das gesamte Programm in einen Schritt-für-Schritt-Algorithmus entschlüsseln.

• Sortieren Sie diese beiden Arrays in aufsteigender Reihenfolge.

• Vergleicht die Elemente zweier Arrays, beginnend mit dem ersten Eintrag jedes Arrays.

• Wenn das Element des kleineren Arrays kleiner oder gleich dem entsprechenden Element im größeren Array ist, fahren Sie mit dem nächsten Element in beiden Arrays fort.

• Wenn die Elemente des kleineren Arrays größer sind als die entsprechenden Elemente im größeren Array, geben Sie „false“ zurück, da das kleinere Array nicht in das größere Array passt.

• Gibt „true“ zurück, wenn alle Elemente des kleineren Arrays kleiner oder gleich den entsprechenden Elementen im größeren Array sind, da das kleinere Array in das größere Array passen kann.

Hinweis− Aufgrund des Sortierschritts beträgt die Komplexität dieses Algorithmus O(n log n), wobei n die Größe des Arrays ist.

Beispiel

C++-Code-Implementierung: Überprüfen Sie, ob ein Array in ein anderes Array passt, indem Sie die Elemente im Array neu anordnen

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

Ausgabe

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

Komplexität

Zeitliche Komplexität: O(n log n), denn in diesem Code sortieren wir zuerst die beiden Arrays und führen dann eine Iteration durch.

Raumkomplexität: O(n), weil wir die Elemente zweier Vektoren im Speicher speichern.

Fazit

In diesem Artikel haben wir versucht, die Methode zu erklären, mit der überprüft wird, ob ein Array in ein anderes Array passt. Ich hoffe, dieser Artikel hilft Ihnen, dieses Konzept besser zu verstehen.

Das obige ist der detaillierte Inhalt vonÜberprüfen Sie, ob ein Array in ein anderes Array passt, indem Sie die Elemente im Array neu anordnen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!