Optimale Suche nach k Minimalwerten in unsortierten Liste von ganzen Zahlen

Question

Ich wurde gerade mit einer Frage interviewt, und ich bin gespannt, was die Antwort sein sollte. Das Problem war im Wesentlichen:

Angenommen, Sie haben eine unsortierte Liste von n ganzen Zahlen. Wie finden Sie die k Mindestwerte in dieser Liste? Das heißt, wenn Sie eine Liste von [10, 11, 24, 12, 13] haben und nach den 2 Mindestwerten suchen, erhalten Sie [10, 11].

Ich habe eine O (n * log (k)) Lösung, und das ist mein Bestes, aber ich bin gespannt, was andere Leute kommen. Ich werde davon absehen, die Gehirne der Leute zu verschmutzen, indem ich meine Lösung poste und sie in kurzer Zeit bearbeiten werde.

EDIT # 1: Zum Beispiel eine Funktion wie: Liste getMinVals (Liste & l, int k)

EDIT # 2: Es sieht aus wie es ein Auswahlalgorithmus ist, also werde ich in meiner Lösung werfen auch; Iterieren über die Liste und Verwenden einer Prioritätswarteschlange zum Speichern der Mindestwerte. Die Spezifikation für die Prioritätswarteschlange bestand darin, dass die Maximalwerte an der Spitze der Prioritätswarteschlange landen würden. Beim Vergleich des Oberteils mit einem Element würde daher der Oberkopf aufgeklappt und das kleinere Element verschoben. Dies nahm an, dass die Prioritätswarteschlange einen O (log n) -Push und einen O (1) -Pop hatte.

Answer 1

Dies ist der quickSelect Algorithmus. Es ist im Grunde eine schnelle Art, bei der Sie nur für einen Teil des Arrays rekursiv sind. Hier ist eine einfache Implementierung in Python, die eher der Kürze und Lesbarkeit halber geschrieben wurde als der Effizienz.

def quickSelect(data, nLeast) : 
    pivot = data[-1] 
    less = [x for x in data if x <= pivot] 
    greater = [x for x in data if x > pivot] 
    less.append(pivot) 

    if len(less) < nLeast : 
     return less + quickSelect(greater, nLeast - len(less)) 
    elif len(less) == nLeast : 
     return less 
    else : 
     return quickSelect(less, nLeast) 

Dies wird in O (N) im Durchschnitt läuft, bei jeder Iteration, da Sie erwartet werden, um die Größe von data durch eine multiplikative Konstante zu reduzieren. Das Ergebnis wird nicht sortiert. Der schlechteste Fall ist O (N^2), aber dies wird im Wesentlichen genauso gehandhabt wie eine schnelle Sortierung, die Dinge wie Median-von-3 verwendet.

Answer 2

Dies ist normalerweise in den Algorithmus Bücher unter selection algorithms oder "lineare Auswahl". Hier ist die spezifische section on min/max k values in a list. Es ist O (nlog (k)).