. Kleinste Bereichsabdeckungselemente aus K-Listen

632. Kleinste Bereichsabdeckungselemente aus K-Listen

Schwierigkeit:Schwer

Themen: Array, Hash-Tabelle, Greedy, Schiebefenster, Sortierung, Heap (Prioritätswarteschlange)

Sie haben k Listen sortierter Ganzzahlen in nicht absteigender Reihenfolge. Finden Sie den kleinsten Bereich, der mindestens eine Zahl aus jeder der k-Listen enthält.

Wir definieren, dass der Bereich [a, b] kleiner ist als der Bereich [c, d], wenn b – a < d - c oder a < c wenn b - a == d - c.

Beispiel 1:

• Eingabe: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
• Ausgabe: [20,24]
• Erklärung:
  • Liste 1: [4, 10, 15, 24,26], 24 liegt im Bereich [20,24].
  • Liste 2: [0, 9, 12, 20], 20 liegt im Bereich [20,24].
  • Liste 3: [5, 18, 22, 30], 22 liegt im Bereich [20,24].

Beispiel 2:

• Eingabe: nums = [[1,2,3],[1,2,3],[1,2,3]]
• Ausgabe: [1,1]

Einschränkungen:

• nums.length == k
• 1 <= k <= 3500
• 1 <= nums[i].length <= 50
• -10⁵ <= nums[i][j] <= 10⁵
• nums[i] wird in nicht abnehmender Reihenfolge sortiert.

Lösung:

Wir können einen Min-Heap (oder eine Prioritätswarteschlange) verwenden, um das kleinste Element aus jeder Liste zu verfolgen und gleichzeitig ein Schiebefenster aufrechtzuerhalten, um den kleinsten Bereich zu finden, der mindestens ein Element aus jeder Liste enthält.

Ansatz

1. Min-Heap-Initialisierung: Verwenden Sie einen Min-Heap, um die aktuellen Elemente aus jeder der k Listen zu speichern. Jeder Heap-Eintrag ist ein Tupel, der den Wert, den Index der Liste, aus der er stammt, und den Index des Elements in dieser Liste enthält.
2. Max Value Tracking: Verfolgen Sie den Maximalwert im aktuellen Fenster. Dies ist wichtig, da der Bereich durch die Differenz zwischen dem kleinsten Element (aus dem Heap) und dem aktuellen Maximum bestimmt wird.
3. Iterieren bis zum Ende der Listen: Für jede Iteration:
   • Extrahieren Sie das minimale Element aus dem Heap.
   • Aktualisieren Sie den Bereich, wenn der aktuelle Bereich [min_value, max_value] kleiner ist als der zuvor aufgezeichnete kleinste Bereich.
   • Gehen Sie zum nächsten Element in der Liste, aus dem das minimale Element entnommen wurde. Aktualisieren Sie den Maximalwert und fügen Sie das neue Element zum Heap hinzu.
4. Beendigung: Der Prozess endet, wenn eine Liste erschöpft ist.

Lassen Sie uns diese Lösung in PHP implementieren: 632. Kleinste Bereichsabdeckungselemente aus K-Listen

  
  
  Erläuterung:




Heap-Initialisierung:


Der anfängliche Heap enthält das erste Element aus jeder Liste. Wir verfolgen auch das maximale Element unter den ersten Elementen.



Verarbeitung des Heaps:


Extrahieren Sie das minimale Element aus dem Heap und versuchen Sie dann, den Bereich zu erweitern, indem Sie das nächste Element aus derselben Liste hinzufügen (falls verfügbar).
Nachdem Sie dem Heap ein neues Element hinzugefügt haben, aktualisieren Sie den maxValue, wenn das neue Element größer ist.
Aktualisieren Sie den kleinsten Bereich immer dann, wenn die Differenz zwischen maxValue und minValue kleiner ist als der zuvor aufgezeichnete Bereich.



Kündigung:


Die Schleife stoppt, wenn in einer Liste keine Elemente mehr vorhanden sind, da wir nicht mehr alle Listen in den Bereich aufnehmen können.





  
  
  Komplexitätsanalyse




Zeitkomplexität: O(n * log k), wobei n die Gesamtzahl der Elemente in allen Listen und k die Anzahl der Listen ist. Die Komplexität ergibt sich aus dem Einfügen und Entfernen von Elementen aus dem Heap.

Raumkomplexität: O(k) zum Speichern von Elementen im Heap.


Diese Lösung findet effizient den kleinsten Bereich, der mindestens eine Zahl aus jeder der k sortierten Listen enthält.

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 von. Kleinste Bereichsabdeckungselemente aus K-Listen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!