Minimaler Wechsel zu Group All s Together II

2134. Mindestanzahl an Swaps, um alle Einsen zusammenzufassen II

Mittel

EinSwapist definiert als das Einnehmen zweierverschiedenerPositionen in einem Array und das Vertauschen der darin enthaltenen Werte.

EinkreisförmigesArray ist als ein Array definiert, bei dem wir dasersteElement und dasletzteElement alsangrenzendbetrachten.

Geben Sie bei einembinären ZirkelArray-Nummerndie Mindestanzahl an Swaps zurück, die erforderlich sind, um alle im Array vorhandenen Einsen aneinem beliebigen Ortzu gruppieren.

Beispiel 1:

• Eingabe:nums = [0,1,0,1,1,0,0]
• Ausgabe:1
• Erklärung:Hier sind einige Möglichkeiten, alle Einsen zusammenzufassen:
  • [0,0,1,1,1,0,0] mit 1 Swap.
  • [0,1,1,1,0,0,0] mit 1 Swap.
  • [1,1,0,0,0,0,1] mit 2 Swaps (unter Verwendung der kreisförmigen Eigenschaft des Arrays).
  • Es gibt keine Möglichkeit, alle Einsen mit 0 Swaps zu gruppieren.
  • Daher beträgt die Mindestanzahl erforderlicher Swaps 1.

Beispiel 2:

• Eingabe:nums = [0,1,1,1,0,0,1,1,0]
• Ausgabe:2
• Erklärung:Hier sind einige Möglichkeiten, alle Einsen zusammenzufassen:
  • [1,1,1,0,0,0,0,1,1] mit 2 Swaps (unter Verwendung der kreisförmigen Eigenschaft des Arrays).
  • [1,1,1,1,1,0,0,0,0] mit 2 Swaps.
  • Es gibt keine Möglichkeit, alle Einsen mit 0 oder 1 Swaps zusammenzufassen.
  • Daher beträgt die Mindestanzahl der erforderlichen Swaps 2.

Beispiel 3:

• Eingabe:nums = [1,1,0,0,1]
• Ausgabe:0
• Erklärung:Alle Einsen sind aufgrund der kreisförmigen Eigenschaft des Arrays bereits gruppiert.
  • Daher beträgt die Mindestanzahl erforderlicher Swaps 0,

Einschränkungen:

• 1 <= nums.length <= 10⁵
• nums[i] ist entweder 0 oder 1.

Hinweis:

1. Beachten Sie, dass die Anzahl der zu gruppierenden Einsen festgelegt ist. Es ist die Anzahl der Einsen, die das gesamte Array hat.
2. Rufen Sie diese Nummer insgesamt an. Wir sollten dann für jedes Subarray der Gesamtgröße (möglicherweise umwickelt) prüfen, wie viele Swaps erforderlich sind, damit das Subarray nur aus Einsen besteht.
3. Die Anzahl der erforderlichen Swaps ist die Anzahl der Nullen im Subarray.
4. Um die kreisförmige Eigenschaft des Arrays zu beseitigen, können wir das ursprüngliche Array an sich selbst anhängen. Dann überprüfen wir jedes Unterarray auf seine Gesamtlänge.
5. Wie vermeiden wir, jedes Mal die Anzahl der Nullen im Subarray neu zu zählen? Die Sliding Window-Technik kann helfen.

Lösung:

Um dieses Problem zu lösen, können wir die folgenden Schritte ausführen:

1. Zählen Sie die Gesamtzahl der Einsen: Dies ist die Anzahl der Einsen, die wir zum Gruppieren benötigen.
2. Erweitern Sie das Array: Um die kreisförmige Natur zu bewältigen, hängen Sie das Array an sich selbst an.
3. Verwenden Sie die Sliding-Window-Technik: Wenden Sie die Sliding-Window-Technik auf das erweiterte Array an, um die minimal erforderliche Anzahl von Swaps zu ermitteln.

Lassen Sie uns diese Lösung in PHP implementieren:2134. Mindestanzahl an Swaps, um alle Einsen zusammenzufassen II

        
Erläuterung:
        

         
Zählen Sie die Gesamtzahl der Einsen: Berechnen Sie die Gesamtzahl der Einsen im ursprünglichen Array.
         
Erweitern Sie das Array: Verketten Sie das ursprüngliche Array mit sich selbst, um die kreisförmige Natur zu bewältigen.
         
Anfangsfenster: Zählen Sie die Anzahl der Nullen im Anfangsfenster, dessen Größe der Gesamtzahl der Einsen entspricht.
         
Schiebefenster: Schieben Sie das Fenster über das erweiterte Array. Aktualisieren Sie für jede neue Position die Anzahl der Nullen basierend auf den Elementen, die in das Fenster eintreten und es verlassen.
         
Minimum finden: Verfolgen Sie die Mindestanzahl der gefundenen Nullen, was der Mindestanzahl der benötigten Swaps entspricht.
        
Diese Lösung behandelt das kreisförmige Array effizient, indem sie es in ein lineares Problem umwandelt und die Schiebefenstertechnik verwendet, um eine laufende Anzahl von Nullen in jedem Fenster beizubehalten, dessen Größe der Gesamtzahl der Einsen entspricht.
Kontaktlinks
Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, demRepositoryeinen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Eure Unterstützung würde mir sehr viel bedeuten!
Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:
        

         
LinkedIn
         
GitHub
        
Das obige ist der detaillierte Inhalt vonMinimaler Wechsel zu Group All s Together II. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!