Finden Sie die Punktzahl eines Arrays, nachdem Sie alle Elemente markiert haben

2593. Finden Sie die Punktzahl eines Arrays, nachdem Sie alle Elemente markiert haben

Schwierigkeit:Mittel

Themen: Heap (Prioritätswarteschlange), Sortieren, Array, Simulation, Hash-Tabelle, geordneter Satz, geordnete Karte, Greedy, monotoner Stapel, Schiebefenster, zwei Zeiger, Stapel, Warteschlange, Bitmanipulation, Teilen und Erobern, dynamische Programmierung, doppelt verknüpfte Liste, Datenstrom, Radix-Sortierung, Backtracking, Bitmaske, Baum, Design, Hash-Funktion, String, Iterator, Zählsortierung, verknüpfte Liste

Sie erhalten ein Array nums, das aus positiven ganzen Zahlen besteht.

Beginnend mit Punktzahl = 0 wenden Sie den folgenden Algorithmus an:

• Wählen Sie die kleinste Ganzzahl des Arrays, die nicht markiert ist. Bei Gleichstand wählen Sie den mit dem kleinsten Index.
• Fügen Sie den Wert der ausgewählten Ganzzahl zur Bewertung hinzu.
• Markieren das ausgewählte Element und seine beiden angrenzenden Elemente, falls vorhanden.
• Wiederholen Sie den Vorgang, bis alle Array-Elemente markiert sind.

Geben Sie die Punktzahl zurück, die Sie nach Anwendung des obigen Algorithmus erhalten.

Beispiel 1:

• Eingabe: nums = [2,1,3,4,5,2]
• Ausgabe: 7
• Erklärung: Wir markieren die Elemente wie folgt:
  • 1 ist das kleinste unmarkierte Element, daher markieren wir es und seine beiden angrenzenden Elemente: [2,1,3,4,5,2].
  • 2 ist das kleinste unmarkierte Element, daher markieren wir es und sein links angrenzendes Element: [2,1,3,4,5,2].
  • 4 ist das einzige verbleibende unmarkierte Element, also markieren wir es: [2,1,3,4,5,2].
  • Unsere Punktzahl ist 1 2 4 = 7.

Beispiel 2:

• Eingabe: nums = [2,3,5,1,3,2]
• Ausgabe: 5
• Erklärung: Wir markieren die Elemente wie folgt:
  • 1 ist das kleinste unmarkierte Element, daher markieren wir es und seine beiden angrenzenden Elemente: [2,3,5,1,3,2].
  • 2 ist das kleinste unmarkierte Element. Da es zwei davon gibt, wählen wir das am weitesten links stehende Element aus, also markieren wir das bei Index 0 und sein rechts angrenzendes Element: [2,3,5,1,3, 2].
  • 2 ist das einzige verbleibende unmarkierte Element, daher markieren wir es: [2,3,5,1,3,2].
  • Unsere Punktzahl ist 1 2 2 = 5.

Einschränkungen:

• 1 <= nums.length <= 10⁵
• 1 <= nums[i] <= 10⁶

Hinweis:

1. Versuchen Sie, den Prozess der Markierung der Elemente und ihrer angrenzenden Elemente zu simulieren.
2. Wenn es ein Element gibt, das bereits markiert wurde, überspringen Sie es.

Lösung:

Wir können den Markierungsprozess effizient simulieren, indem wir ein sortiertes Array oder eine Prioritätswarteschlange verwenden, um den Überblick über das kleinste unmarkierte Element zu behalten. Wir können also den folgenden Ansatz verwenden:

Planen:

1. Eingabeanalyse: Lesen Sie die Array-Nummern und initialisieren Sie Variablen für die Punktzahl und den Bewertungsstatus.
2. Heap (Prioritätswarteschlange):
   • Verwenden Sie einen Min-Heap, um das kleinste unmarkierte Element in jedem Schritt effizient zu extrahieren.
   • Fügen Sie jedes Element zusammen mit seinem Index (Wert, Index) in den Heap ein, um Bindungen basierend auf dem kleinsten Index zu verwalten.
3. Markierungselemente:
   • Verwalten Sie ein markiertes Array, um zu verfolgen, ob ein Element und seine angrenzenden Elemente markiert sind.
   • Wenn Sie ein Element aus dem Heap verarbeiten, überspringen Sie es, wenn es bereits markiert ist.
   • Markieren Sie das aktuelle Element und seine beiden angrenzenden Elemente (falls vorhanden).
   • Füge den Wert des aktuellen Elements zur Punktzahl hinzu.
4. Wiederholen: Fahren Sie fort, bis alle Elemente markiert sind.
5. Ausgabe: Gibt die kumulierte Punktzahl zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 2593. Finden Sie die Punktzahl eines Arrays, nachdem Sie alle Elemente markiert haben

  
  
  Erläuterung:




Haufenkonstruktion:


Die usort-Funktion sortiert das Array basierend auf Werten und nach Index, wenn Werte verknüpft sind.
Dadurch wird sichergestellt, dass wir immer das kleinste unmarkierte Element mit dem kleinsten Index verarbeiten.



Markierungslogik:


Für jedes nicht markierte Element markieren wir es und seine angrenzenden Elemente mithilfe des markierten Arrays.
Dadurch wird sichergestellt, dass wir zuvor markierte Elemente effizient überspringen.



Zeitkomplexität:


Sortieren des Heaps: O(n log n)

Verarbeitung des Heaps: O(n)

Insgesamt: O(n log n), was für die gegebenen Einschränkungen effizient ist.



Weltraumkomplexität:


Markiertes Array: O(n)

Haufen: O(n)

Gesamt: O(n)





Diese Lösung erfüllt die Einschränkungen und arbeitet effizient für große Eingaben.

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 vonFinden Sie die Punktzahl eines Arrays, nachdem Sie alle Elemente markiert haben. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!