Minimaler Wechsel zu Group All s Together II

2134. Mindestanzahl an Swaps, um alle Einsen zusammenzufassen II

Mittel

Ein Swap ist so definiert, dass er zwei unterschiedliche Positionen in einem Array einnimmt und die darin enthaltenen Werte austauscht.

Ein kreisförmiges Array ist als ein Array definiert, bei dem wir das erste Element und das letzte Element als angrenzend betrachten.

Geben Sie bei einem binären Zirkel Array-Nummern die Mindestanzahl an Swaps zurück, die erforderlich sind, um alle im Array vorhandenen Einsen an beliebiger Position zusammenzufassen.

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 zusammen 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 zusammen mit 0 oder 1 Swaps zu gruppieren.
  • Daher beträgt die Mindestanzahl erforderlicher 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. Nennen Sie diese Zahl insgesamt. Wir sollten dann für jedes Subarray mit 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 zusammenfassen müssen.
2. Erweitern Sie das Array: Um die kreisförmige Natur zu handhaben, 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 erforderlichen 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, 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



          

            
  

            
        
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!