Finden Sie heraus, ob das Array sortiert werden kann

3011. Finden Sie heraus, ob das Array sortiert werden kann

Schwierigkeit:Mittel

Themen: Array, Bitmanipulation, Sortierung

Sie erhalten ein 0-indiziertes Array von positiven ganzen Zahlen.

In einem Vorgang können Sie zwei beliebige benachbarte Elemente austauschen, wenn sie die gleiche Anzahl gesetzter Bits¹ haben. Sie dürfen diesen Vorgang beliebig oft ausführen (einschließlich null).

Gib true zurück, wenn du das Array sortieren kannst, sonst gib false zurück.

Beispiel 1:

• Eingabe: nums = [8,4,2,30,15]
• Ausgabe:wahr
• Erklärung: Schauen wir uns die binäre Darstellung jedes Elements an. Die Zahlen 2, 4 und 8 haben jeweils ein gesetztes Bit mit der binären Darstellung „10“, „100“ bzw. „1000“. Die Zahlen 15 und 30 haben jeweils vier gesetzte Bits mit binärer Darstellung „1111“ und „11110“. Wir können das Array mit 4 Operationen sortieren:
  • Tausche Nums[0] mit Nums[1]. Diese Operation ist gültig, da 8 und 4 jeweils ein gesetztes Bit haben. Das Array wird zu [4,8,2,30,15].
  • Tausche Nums[1] mit Nums[2]. Diese Operation ist gültig, da 8 und 2 jeweils ein gesetztes Bit haben. Das Array wird zu [4,2,8,30,15].
  • Tausche Nums[0] mit Nums[1]. Diese Operation ist gültig, da 4 und 2 jeweils ein gesetztes Bit haben. Das Array wird zu [2,4,8,30,15].
  • Tausche Nums[3] mit Nums[4]. Diese Operation ist gültig, da 30 und 15 jeweils vier gesetzte Bits haben. Das Array wird zu [2,4,8,15,30].
  • Das Array wurde sortiert, daher geben wir true zurück.
  • Beachten Sie, dass es möglicherweise andere Operationssequenzen gibt, die das Array ebenfalls sortieren.

Beispiel 2:

• Eingabe: nums = [1,2,3,4,5]
• Ausgabe:wahr
• Erklärung: Das Array ist bereits sortiert, daher geben wir true zurück.

Beispiel 3:

• Eingabe: nums = [3,16,8,4,2]
• Ausgabe:falsch
• Erklärung:Es kann gezeigt werden, dass es nicht möglich ist, das Eingabearray mit einer beliebigen Anzahl von Operationen zu sortieren.

Beispiel 4:

• Eingabe: nums = [75,34,30]
• Ausgabe:false
• Erklärung:Es kann gezeigt werden, dass es nicht möglich ist, das Eingabearray mit einer beliebigen Anzahl von Operationen zu sortieren.

Einschränkungen:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 2⁸

Hinweis:

1. Teilen Sie das Array in Segmente auf. Jedes Segment enthält aufeinanderfolgende Elemente mit der gleichen Anzahl gesetzter Bits.
2. Von links nach rechts sollte das größte Element des vorherigen Segments kleiner sein als das kleinste Element des aktuellen Segments.

Lösung:

Wir müssen feststellen, ob das Array sortiert werden kann, indem nur benachbarte Elemente ausgetauscht werden, die in ihrer Binärdarstellung die gleiche Anzahl gesetzter Bits haben. Hier ist der Plan:

Lösungsschritte:

1. Schlüsselbeobachtung: Die Operation ermöglicht es uns, benachbarte Elemente nur dann auszutauschen, wenn sie die gleiche Anzahl gesetzter Bits haben. Dadurch wird der Austausch zwischen Elementen mit unterschiedlicher Anzahl gesetzter Bits eingeschränkt.

2. Planen:

   • Gruppieren Sie Elemente nach der Anzahl der gesetzten Bits in ihrer Binärdarstellung.
   • Sortieren Sie jede Gruppe einzeln, da Elemente innerhalb einer Gruppe durch Austauschen neu angeordnet werden können.
   • Nachdem Sie jede Gruppe sortiert haben, führen Sie die sortierten Gruppen wieder zusammen.
   • Überprüfen Sie, ob dieses zusammengeführte Array sortiert ist. Wenn dies der Fall ist, ist das Sortieren des Arrays mithilfe der zulässigen Operationen möglich.

3. Schritte:

   • Zählen Sie die gesetzten Bits in jeder Nummer und gruppieren Sie Nummern mit derselben gesetzten Bitanzahl.
   • Jede Gruppe einzeln sortieren.
   • Rekonstruieren Sie das Array aus diesen sortierten Gruppen und überprüfen Sie, ob das Ergebnis sortiert ist.

Lassen Sie uns diese Lösung in PHP implementieren: 3011. Finden Sie heraus, ob das Array sortiert werden kann

  
  
  Erläuterung:




CountSetBits-Funktion: Zählt die Anzahl der gesetzten Bits in einer Zahl mithilfe bitweiser Operationen.

Gruppierungselemente: bitGroups ist ein assoziatives Array, bei dem jeder Schlüssel die festgelegte Bitanzahl darstellt und jeder Wert ein Zahlenarray mit so vielen gesetzten Bits ist.

Sortieren und Neuaufbau:


Wir iterieren über Nummern, um Elemente nach ihrer festgelegten Bitanzahl zu gruppieren.
Wir sortieren jede Gruppe einzeln.
Wir rekonstruieren dann das Array, indem wir jedes sortierte Gruppenelement in seiner ursprünglichen Reihenfolge einfügen.
Zuletzt prüfen wir, ob das rekonstruierte Array in nicht absteigender Reihenfolge sortiert ist. Wenn ja, geben Sie true zurück. Andernfalls geben Sie false zurück.


Endgültiger Vergleich: Vergleichen Sie das neu erstellte Array mit einer vollständig sortierten Version von Nums. Wenn sie übereinstimmen, wird „true“ zurückgegeben. andernfalls wird false zurückgegeben.



  
  
  Komplexitätsanalyse




Zeitkomplexität: O(n log n) aufgrund der Sortierung innerhalb jeder Gruppe und des abschließenden Vergleichs.

Raumkomplexität: O(n) zum Speichern der Bitgruppen.


Diese Lösung stellt sicher, dass wir nur benachbarte Elemente mit der gleichen eingestellten Bitanzahl austauschen und möglichst eine sortierte Reihenfolge erreichen.

Kontaktlinks
Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub








Bit setzen Ein gesetztes Bit bezieht sich auf ein Bit in der binären Darstellung einer Zahl, das den Wert 1 hat. ↩





          

            
  

            
        
Das obige ist der detaillierte Inhalt vonFinden Sie heraus, ob das Array sortiert werden kann. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!