|
|
| 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.
__________________
I'm 71% Megatron!
|
|
