Kleinster Bereich, der mindestens eine Zahl aus jeder der k Listen enthält

Question

Kleinster Bereich, der mindestens eine Zahl aus jeder der k Listen enthält

8

Sie haben k Listen sortierter Ganzzahlen. Suchen Sie den kleinsten Bereich, der mindestens eine Zahl aus jeder der k -Listen enthält.

Zum Beispiel

%Vor%

Der kleinste Bereich hier wäre [14, 18] , da er 14 von list 1 , 15 von list 2 und 18 von list 3 enthält.

Mein Ansatz ist:

Verwenden Sie einfach einen MinHeap und fügen Sie die ersten Elemente aus K lists
Entfernen Sie das Element min und fügen Sie das nächste Element aus der entsprechenden Liste hinzu
Verfolgen Sie gleichzeitig den maximalen und minimalen Wert, so dass wir den minimalen Bereich berechnen können

Aber das einzige Problem, mit dem ich zu tun habe, ist: Angenommen, für eine Liste gibt es keine Elemente mehr, als sollte ich dort enden oder sollte ich fortfahren?

algorithm java data-structures

Trying 15.01.2014, 10:19

quelle

2 Antworten

Tags und Links algorithm java data-structures

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Zwei Aufrufe derselben Methode mit einem anderen Methodenaufruf zwischenzeitlich, wenn die Reihenfolge wichtig ist, in Mockito überprüfen

score 5 · Answer 1

Sehr schöner O (n log n) -Algorithmus!

Sie können dort enden, weil Sie nie das bessere Intervall finden werden, das den gegebenen Zustand "Bereich, der mindestens eine Zahl von jeder der k Listen enthält" erfüllt.

Angenommen, Sie verlassen das aktuelle Minimum m (das letzte Element aus einer Liste) und entfernen stattdessen etwas (nicht das Minimum) aus einer anderen Liste. In diesem Fall kann der Bereich nur wachsen (weil das Minimum des Bereichs durch m bestimmt wird). Es macht also keinen Sinn, den Algorithmus zu stoppen.

score 0 · Answer 2

Nein, das ist nicht Ihre Endbedingung. Schau dir dieses Beispiel an:

%Vor%

Der Bereich ist ziemlich klar [0,1] , aber wenn Sie aufgehört haben, sobald Sie eine leere Liste gefunden haben, würden Sie [0,0] zurückgeben.

Sie können also nur aufhören, wenn Sie wissen, dass Sie Werte aus allen k lists gesehen haben und in einer der Listen keine Einträge mehr vorhanden sind. Wenn Sie die Min- und Max-Werte für jede Liste separat verfolgen, sollte das ziemlich einfach sein, da Sie einfach sicherstellen können, dass es für jede Liste einen Min- und Max-Wert gibt.