k-kleinste Zahl aus zwei Arrays |
| 07.12.2007, 10:57 | Auf diesen Beitrag antworten » |
| JROppenheimer | k-kleinste Zahl aus zwei Arrays Tach ihr Leut, ich hab ein Problem, und das ist meien Ideenlosigkeit. Gegeben sind zwei Arrays A,B der länge n (also beide gleichlang, gefüllt mir irgendwelchen Zahlen schätze ich, ist nicht mehr angegeben). Gesucht ist nun die n-kleinste Zahl unter allen 2n Zahlen. Man hat nur die Möglichkeit mit X.query(k) die k-kleinste Zahl aus A oder B zu erfragen. Gesucht ist ein Algorithmus, der in O(log(n)) de n-kleinste Zahl bestimmt. Da ich x*log(n) zur Verfügung habe (mit x konstant) dachte ich mir, das ist bestimm was rekursives. Wenn ich die Arrays irgendwie immer halbieren würde, wäre es sowas wie log2(n), da dachte ich an die binäre Suche. Das heisst aber, dass ich doch über die Indize der Arrays arbeiten müsste, oder? Ich bin wirklich ideenlos, für einen Tip wäre ich sehr dankbar. |
|
|
|
| 08.12.2007, 21:59 | Auf diesen Beitrag antworten » |
| Crotaphytus | So was wie binäre Suche heißt ja, dass du im ersten Schritt die n/2-kleinste Zahl suchst. Die kannst du doch mit der query-Methode direkt erfragen. Und noch ein Tipp: Die n-te kleinste Zahl von 2n Zahlen ist der Median dieser Folge. Das heißt, es gibt genauso viel Zahlen die größer sind wie Zahlen die kleiner sind. Damit sollte dir mit deinem Binäre-Suche-Ansatz eigentlich klar werden können, was du jeweils wegschmeißen kannst. |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
|
