632. Kleinste Reichweite, die Elemente aus K -Listen abdecken

Schwierigkeit: hard

Themen: Array, Hash -Tabelle, Giery, Schiebfenster, Sortieren, Heap (Prioritätswarteschlange)

Sie haben K-Listen sortierter Ganzzahlen in nicht dekretierender Order . Finden Sie den kleinsten Bereich, der mindestens eine Nummer aus jedem der K -Listen enthält.

Wir definieren den Bereich [a, b] kleiner als Bereich [c, d] if b - a oder a

Beispiel 1:

• input: nums = [4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
• output: [20,24]
• Erläuterung:
  • Liste 1: [4, 10, 15, 24,26], 24 ist in Reichweite [20,24].
  • Liste 2: [0, 9, 12, 20], 20 ist in Reichweite [20,24].
  • Liste 3: [5, 18, 22, 30], 22 ist in Reichweite [20,24].

Beispiel 2:

• input: nums = [[1,2,3], [1,2,3], [1,2,3]]
• output: [1,1]

Einschränkungen:

• nums.length == k
• 1
• 1
• -10 ⁵ 5
• nums [i] ist sortiert in nicht dekreting order.

Lösung:

Wir können eine min-heap (oder vorrangige Warteschlange) verwenden, um das kleinste Element aus jeder Liste zu verfolgen, während wir ein Schiebefenster beibehalten, 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 jedem der K-Listen zu speichern. Jeder Heap -Eintrag ist ein Tupel, das den Wert, den Index der Liste enthält, aus dem er stammt, und der Index des Elements in dieser Liste.
2. Max Value Tracking : Verfolgen Sie den maximalen Wert im aktuellen Fenster. Dies ist wichtig, da der Bereich durch den Unterschied zwischen dem kleinsten Element (vom Haufen) und dem aktuellen Maximum bestimmt wird.
3. iterieren Sie 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.
   • wechseln Sie zum nächsten Element in der Liste, aus der das Mindestelement entnommen wurde. Aktualisieren Sie den maximalen Wert und fügen Sie das neue Element dem Heap hinzu.
4. terminierung : Der Prozess endet, wenn eine Liste erschöpft ist.

Lassen Sie uns diese Lösung in PHP implementieren: 632. Kleinste Reichweite, die Elemente aus K -Listen abdecken

Erläuterung:

1. Heap Initialisierung :
   • Der anfängliche Heap enthält das erste Element aus jeder Liste. Wir verfolgen auch das maximale Element unter den ersten Elementen.
2. verarbeiten die heap :
   • 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).
   .
   • Nach dem Hinzufügen eines neuen Elements zum Heap aktualisieren Sie den MaxValue, wenn das neue Element größer ist.
   • Aktualisieren Sie den kleinsten Bereich, wenn der Unterschied zwischen MaxValue und MinValue kleiner als der zuvor aufgezeichnete Bereich ist.
3. Beendigung:
   • Die Schleife stoppt, wenn eine Liste die Elemente ausgeht, da wir nicht mehr alle Listen im Bereich aufnehmen können.

Komplexitätsanalyse

• Zeitkomplexität : o (n * log k), wobei n die Gesamtzahl der Elemente in allen Listen ist und K die Anzahl der Listen ist. Die Komplexität kommt vom Einsetzen 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 Nummer aus jeder der k -sortierten Listen enthält.

wenden Sie sich an links

Wenn Sie diese Serie hilfreich gefunden haben, sollten Sie den repository einen Stern auf Github geben oder den Beitrag in Ihren Lieblingsnetzwerken teilen? Ihre Unterstützung würde mir viel bedeuten!

Wenn Sie mehr hilfreiche Inhalte wie diesen wünschen, können Sie mir gerne folgen:

• linkedIn
• github