ich habe eine Frage zu einer Aufgabe, in der es darum geht, das k-größte Element einer unsortierten Liste in der Laufzeit O(n*log(k)) zurückzugeben, also das k = 1 größte Element ist das größte Element, das k = 2 größte Element ist das zweitgrößte, etc.
In der Aufgabe stand zwar etwas davon, man könne Min/Max-Heaps verwenden, oder mehrfache Heaps, und dass die Laufzeit O(n + k*Log(k)) (=O(n)?) auch akzeptabel sei. Ich habe versucht das ganz über Radix-LSD zu lösen, schicke hier einfach mal die def rein. Nun frage ich mich nur im Nachhinein, ob das innerhalb der besagten Komplexität wäre? Außerdem würde ich auch gerne wissen, welche Lösung mit Heaps richtig gewesen wäre? Ich habe ursprünglich versucht die Liste zu einem Heap zu überführen (also einen Heapanteil definieren durch eine Laufvariable i, die von len(l) bis 0 jeweils das Element solange an die (i-1)//2 te Stelle tauscht, bis das (i-1)//2-te Element entweder größer ist, oder man am ersten Index ist. Dadurch würde sich dann ein Max Heap ergeben in O(n), von dem man dann das größte Element extrahiert, also immer das an 0ter Stelle und dann das letzte an die erste Stelle tauscht und heapify Down darauf aufruft (log(n)). Das ganze k mal, dann hat man das k-größte Element. Wäre dann halt eher in O(k*log(n)). Deswegen habe ich es über Radix probiert:
Code: Alles auswählen
def k_greates_elem(l,k):
def radix(l): #Gewünschte Laufzeit ist n*log(k), hier durch Radix Sort
iter = 1
goon = True
while goon:
lSol = []
for _ in range(10): #erstmal wird die Liste in die Buckets von 1-9 eingeteilt, dafür nehme ich eine Hilfsliste lSol
lSol += [[]]
if goon:
abbr = False
for elem in l:
if elem > (10 * iter): #Hier wird auch gleich nach der Abbruchbedingung geguckt, ob kein Element größer als das Modulo ist
abbr = True
lSol[elem % (10 * iter)] += [elem] #Das Einsortieren erfolgt nach Index. Dies passiert in n Schritten pro Iteration. Da der Modulo jedes mal /10 geteilt wird
if not abbr: # wird dies log(k) (log Base 10) mal wiederholt
goon = False
iter *= 10
l = []
for h in lSol: #der Einfachheit halber wandel ich jedes mal wieder zur "normalen" Liste um, dann wieder zu lSol usw.
l += h
return l
l = radix(l) #sortierte Liste, das k-größte Element ist das an der len(l) - k-ten Stelle. Die Zugriffszeit auf Listenindexe ist konstant
return l[len(l)-k] #Also ist der Algorithmus aus O(n*log(k)) (Base 10)
l = [3,4,1,9,2,5]
print(k_greates_elem(l,5))
:
Wie gesagt, Python-Programmierer denken da als erstes an die eingebaute `iter()`-Funktion mit der man von iterierbaren Objekten einen Iterator bekommen kann.
