Algorithmus: k-kleinste Elemente in k Listen
Hallo,
ich hoffe auf ein wenig Hilfe bei folgender Aufgabe:
Ich habe k aufsteigend sortierte Listen L1...Lk dergleichen Länge. Ich will über alle Listen hinweg die k kleinsten Elemente auslesen. Problem daran ist, dass es asymptotisch echt schneller als k² sein soll, das heißt der mir logische Weg funktioniert nicht.
Wäre über einen Denkanstß erfreut,
danke!
edit: hat sich erledigt, manchmal kann die lösung auf der hand liegen... (kann geschlossen werden).
für die interessierten: bastel einen heap mit den k jeweils 1. elementen, wenn ein element entfernt wird ersetze es durch das nächste aus der entsprechenden liste... führe k-mal deleteMin aus => k*log(k).
|