Wir haben zwei Datenbanken der Größe n, die Zahlen ohne Wiederholungen enthalten. Also, insgesamt haben wir 2n Elemente. Sie können über eine Abfrage auf jeweils eine Datenbank zugegriffen werden. Die Abfrage ist so, dass Sie ihr ein k geben, und sie gibt den kleinsten Eintrag in dieser Datenbank zurück. Wir müssen den kleinsten Eintrag unter allen 2n Elementen in O (logn) Abfragen finden. Die Idee ist, Teile und herrsche zu gebrauchen, aber ich brauche etwas Hilfe, um darüber nachzudenken. Danke!
So habe ich das durchdacht. Da es sich um ein Bildungsproblem handelt, schlage ich vor, dass Sie aufhören zu lesen, wenn einer der Punkte Sie zum Nachdenken bringt: "Aha, daran hatte ich nicht gedacht, ich kann selbst weiter in diese Richtung denken".
1) Gleiche Beobachtung wie bei sdcwc: Mit einer möglichen leichten Frage darüber, ob sie bei 0 oder 1 beginnt, kann man sich die Datenbank als sortiertes Array vorstellen. Ich frage nach Element 0, ich bekomme das kleinste. Ich frage nach 12, ich bekomme den 13. Kleinsten. Und so weiter. Ich finde das leichter zu visualisieren.
2) Wir wissen, dass wir nach einem O (log n) -Algorithmus suchen. Das heißt, grob gesagt suchen wir nach einem von zwei Dingen:
Entweder beginnen wir damit, das kleinste Element zu berechnen, berechnen dann das zweitkleinste, das viertkleinste, das achte usw., bis wir die gewünschte Größe erreicht haben, und zwar jeden Schritt in konstanter Zeit. Das klingt für mich nicht vielversprechend.
Oder wir beginnen mit einem Problem der Größe n und führen dann eine Operation mit konstanter Zeit durch, die es uns ermöglicht, das ursprüngliche Problem zu lösen, indem wir ein Problem der Größe n / 2 lösen. Offensichtlich können wir das Problem für n = 1 in konstanter Zeit lösen, um den Algorithmus zu vervollständigen. Das klingt ein bisschen plausibler.
Eigentlich muss es nicht immer n / 2 sein. Es könnte n / 3 oder 999 * n / 1000 sein, und das Ergebnis wird immer noch O (log n) sein. Aber es ist kein Nachteil, zuerst nach n / 2 zu suchen.
3) Wie werden wir das Problem so reduzieren? Nun, wenn wir m Elemente vom Anfang des einen oder des anderen Arrays als kleiner als das k-kleinste abstufen / entfernen können, dann können wir das (km) kleinste Element des resultierenden Paars von Arrays finden, und es wird das sein kth kleinste der ursprünglichen Arrays.
4) Schließlich ist die bahnbrechende Beobachtung, dass, wenn das m-kleinste Element der Anordnung A kleiner ist als das m-te kleinste Element der Anordnung B, das m-te Element von A nicht das (2m) kleinste Element der beiden sein kann Arrays kombiniert. Es ist kleiner als das (oder gleichwertig: Ich bin mir nicht sicher, ob "keine Wiederholungen" "keine Wiederholungen in jeder Datenbank" oder "keine Wiederholungen zwischen den kombinierten Datenbanken" bedeutet), da es höchstens 2 * (m- 1) Elemente streng kleiner als in beiden Arrays kombiniert.
Wenn ich keinen Fehler gemacht habe, ist der Rest codiert. Mit einem kleinen zusätzlichen Argument, um den Aus-durch-1 zu berücksichtigen, wenn k ungerade ist, ist diese Lösung tatsächlich O (log k), was 0 (log n) ist, da k & lt; = 2 · n.
Ich habe dieses Problem vor nicht allzu langer Zeit bei einer Eignungsprüfung gesehen, und es riecht nach einem Hausaufgabenproblem. Ich werde daher nur zwei Vorschläge machen:
Studieren Sie die binäre Suche, wobei Sie sorgfältig auf die genaue Natur der Schleifeninvarianten achten. Jon Bentleys Buch Programming Pearls hat eine gute Erklärung
Versuchen Sie, die Invarianten für die binäre Suche zu verallgemeinern.
Zeichnen Sie ein Bild mit verschiedenen Sonderfällen:
Das ist ein ziemlich schweres Problem; Sie werden es leichter haben, wenn Sie direkt auf einen Beweis der Richtigkeit gehen.
Tags und Links algorithm divide-and-conquer