Überprüft, ob das angegebene Array durch Halbierung der Elemente eine Permutation von 1 bis N bilden kann

Unser Ziel besteht darin, festzustellen, ob durch die Durchführung mehrerer Divisionen für jedes im Array enthaltene Element eine Liste mit ganzen Zahlen von 1 bis N ohne Duplikate erstellt wird. Der Erfolg dieser Bemühungen bedeutet, dass unsere Ermittlungsziele erfolgreich erreicht wurden. Der Hauptschwerpunkt unserer Arbeit besteht im Wesentlichen darin, festzustellen, ob das Schneiden aller in einem bestimmten Array bereitgestellten Elemente um zwei zu einer Permutation führen würde, die vollständig aus sich nicht wiederholenden Werten zwischen 1 und N besteht. Sobald dies bestätigt ist, wäre die Bewertung unseres Papiers der nächste logische Schritt.

Grammatik

Bevor wir uns mit unserem Lösungsvorschlag befassen, ist es wichtig, ein grobes Verständnis der Syntax der Methode zu haben, die wir implementieren möchten.

bool canBePermutation(vector<int>& arr)
{
   // Implementation goes here
}
</int>

Algorithmus

Um dieses Problem zu lösen, gehen wir Schritt für Schritt mit dem unten beschriebenen Algorithmus vor -

• Um genau auf die beobachteten Komponenten in einem Array zu achten, beginnen Sie mit dem Starten einer Sammlung oder eines Hash-Sets. Dann iterieren Sie über jedes in diesem Array vorhandene Element.

• Um eine ganze Zahl zwischen 1 und N zu erhalten, müssen Sie jedes Element mehrmals durch 2 dividieren.

• Überprüfen Sie, ob der Ergebniswert bereits in der Sammlung vorhanden ist. Wenn ja, wird „false“ zurückgegeben, da die Anordnung keine Duplikate enthalten darf.

• Damit das Array eine gültige Anordnung ist, muss jedes Element die oben genannten Bedingungen erfüllen. Unter der Annahme, dass dieses Kriterium vollständig erfüllt ist, kann die Bestätigung seiner Berechtigung durch Angabe eines echten Rückgabewerts als angemessene Vorgehensweise angesehen werden.

Methode

Um dieses Problem effektiv zu lösen. Es kann hilfreich sein, verschiedene Strategien auszuprobieren. Ich werde zwei mögliche Ansätze vorschlagen -

Methode 1: Satzbasierter Ansatz

Die Erstellung eines effizienten Ansatzes erfordert den Einsatz sorgfältiger Techniken, wie z. B. die Implementierung eines Tracking-Systems mithilfe von Sammlungen, die erstellt werden, um die während des Prozesses angetroffenen Komponenten aufzuzeichnen. Dabei wird jede Komponente durch einen Divisionsprozess iterativ ausgewertet, um sicherzustellen, dass der resultierende Wert zwischen 1 und N Bereichswerten liegt. Anschließend wird unser Trace-Set auf Validierung überprüft, bevor das neu beobachtete Element angehängt wird. Bei Anomalien wird dann „false“ zurückgegeben, andernfalls wird „false“ zurückgegeben true, sobald alle Werte die von Constellation geforderten Bewertungsprüfungen bestanden haben.

Beispiel

#include <iostream>
#include <vector>
#include <unordered_set>

bool canBePermutation(std::vector<int>& arr) {
   std::unordered_set<int> seen;
   
   for (int num : arr) {
      while (num > 0 && num != 1) {
         if (seen.find(num) != seen.end())
            return false;
         
         seen.insert(num);
         num /= 2;
      }
      
      if (num == 0)
         return false;
   }
   
   return true;
}

int main() {
   std::vector<int> arr = {4, 2, 1, 3};
   
   if (canBePermutation(arr)) {
      std::cout << "The given array can be transformed into a permutation.";
   } else {
      std::cout << "The given array cannot be transformed into a permutation.";
   }
   
   return 0;
}

Ausgabe

The given array cannot be transformed into a permutation.

Anleitung

Die ersten Schritte von Methode 1 umfassen das Einrichten einer ungeordneten Menge, um den Überblick über die im Array vorhandenen Elemente zu behalten. Diese Codierungsmethode iteriert dann weiter über jedes Element im selben Array, dividiert sie jedes Mal durch 2 und reduziert sie wiederholt auf eine ganze Zahl zwischen 1 und N. Während dieser Iterationen wird überprüft, ob ein scheinbar erstelltes Element bereits in derselben Sammlung erstellt wurde. Dadurch wird versucht, doppelte Permutationen einfach aufgrund von Duplikaten zu vermeiden. Wenn ein Duplikat erkannt wird, das aus diesen sich wiederholenden Permutationen resultiert, wird „false“ zurückgegeben, wie wenn alles überprüft wird, ohne dass ein Duplikat vervollständigt wurde – als „true“ übergeben – was effektiv angibt, ob die gegebene Menge in ihre jeweilige Permutation verschoben werden kann, während ihre Komponenten durch Halbierung minimiert werden ihnen.

Methode 2: Sortiermethode

Aufsteigende Sortierung hilft zu erkennen, ob jedes Array-Element sich selbst als passender Wert in der sortierten Liste darstellen kann. Wenn keines der Elemente dieses Kriterium erfüllt, liefert unsere Ausgabe „falsch“. Wenn jedoch alle Elemente diesen Test bestehen, wird „true“ zurückgegeben.

Beispiel

#include <iostream>
#include <vector>
#include <algorithm>

bool canBePermutation(std::vector<int>& arr) {
   std::sort(arr.begin(), arr.end());

   for (int i = 0; i < arr.size(); i++) {
      int expected = i + 1;
      while (arr[i] > 0 && arr[i] != expected)
         arr[i] /= 2;

      if (arr[i] != expected)
         return false;
   }
   
   return true;
}

int main() {
   std::vector<int> arr = {4, 2, 1, 3};
   
   if (canBePermutation(arr)) {
      std::cout << "The given array can be transformed into a permutation.";
   } else {
      std::cout << "The given array cannot be transformed into a permutation.";
   }
   
   return 0;
}

Ausgabe

The given array can be transformed into a permutation.

Anleitung

Gemäß Methode 2 (Sortiermethode) sortieren wir zunächst das ursprüngliche Eingabearray in aufsteigender Reihenfolge, bevor wir die Coderoutine weiter überprüfen. Der Code führt dann verschiedene Iterationen für jedes einzelne Element des obigen Arrays durch und prüft dabei, ob sie durch zwei teilbar sind, bis sie einen angegebenen und angenommenen Wert erreichen, der auf der Grundlage ihrer Position innerhalb des neu sortierten Bereichs der Indexwertpositionen festgelegt wird. Sollte es in einer solchen Iteration Fälle geben, die diese vordefinierten Schlüsselbedingungen nicht erfüllen, dann beschreibt unser Code das Ergebnis als „False“, was bedeutet, dass es nicht möglich ist, dieses Array in die entsprechende sequentielle Anordnung zu konvertieren. Gleichzeitig erzeugt umgekehrt jedes konforme Element ein „wahres“ Ergebnis, das eine realisierbare positive Richtung für unsere Array-Reorganisationsziele vorgibt.

Fazit

In diesem Beitrag befassen wir uns mit der Herausforderung, zu überprüfen, ob ein bestimmtes Array durch Halbierung seiner Elemente in eine Permutation umgewandelt werden kann, die Zahlen im Bereich von 1 bis N enthält. Wir stellen dem Leser die Gliederung, Syntax und algorithmischen Verfahren zur effizienten Lösung dieses Problems zur Verfügung. Darüber hinaus stellen wir zwei mögliche Ansätze zusammen mit vollständigen Beispielen für ausführbaren C++-Code bereit. Durch die Anwendung der in diesem Artikel hervorgehobenen satzbasierten Techniken oder Sortierstrategien kann der Leser zu seiner Zufriedenheit feststellen, ob ein bestimmtes Array alle notwendigen Bedingungen für eine rechtliche Vereinbarung erfüllt.

Das obige ist der detaillierte Inhalt vonÜberprüft, ob das angegebene Array durch Halbierung der Elemente eine Permutation von 1 bis N bilden kann. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!