nth kleinste Zahl unter den beiden Datenbanken der Größe n jeweils unter Verwendung teile und herrsche [geschlossen]

Question

  

Wir haben zwei Datenbanken der Größe n mit Zahlen ohne Wiederholungen. Also, insgesamt haben wir 2n Elemente. Sie können zu einem Zeitpunkt durch eine Abfrage an eine Datenbank zugegriffen werden. Die Abfrage ist so, dass man ihm ein k geben und es gibt KTH kleinsten Eintrag in dieser Datenbank. Wir brauchen n-ten kleinsten Eintrag unter allen 2n Elemente in O (log n) Abfragen finden.

Die Idee ist, teile und herrsche zu verwenden, aber ich brauche Hilfe Denken durch diese. Dank!

Answer 1

Hier ist, wie ich dachte, das durch. Da es sich um ein Bildungsproblem ist, schlage ich vor, lesen Sie zu stoppen, wenn eine der Punkte macht denken Sie, „Aha, ich hatte nicht gedacht, kann ich glaube, weiter in diese Richtung von mir“.

1) gleiche Beobachtung wie sdcwc: mit einer möglichen leichten Wortklauberei darüber, ob es bei 0 oder 1 beginnt, kann die Datenbank als ein sortiertes Array gedacht werden. Ich bitte um das Element 0, I die kleinsten bekommen. Ich bitte um 12, bekomme ich die 13. kleinste. Und so weiter. Ich finde diese leichter sichtbar zu machen.

2) Wir wissen, dass wir für einen O (log n) Algorithmus suchen. Das bedeutet, dass wir suchen eines von zwei Dingen grob gesagt:

• Entweder wir beginnen, indem das kleinste Element zu berechnen, dann berechnen Sie die 2. kleinste, 4. kleinste, 8., usw., bis wir auf die Größe sind bis wir jeden Schritt in konstanten Zeit wollen. Das klingt nicht mir viel versprechend.

• Oder wir mit einem Problem der Größe beginnen n dann wir einigen konstanten Zeitbetrieb durchführen, die uns das ursprüngliche Problem lösen kann, indem ein Problem der Größe der Lösung n / 2. Natürlich können wir das Problem für n = 1 in konstanter Zeit lösen, um den Algorithmus abzuschließen. Das klingt ein wenig plausibel.

Eigentlich ist es nicht unbedingt n / 2 jedes Mal sein. Es könnte sein, n / 3 oder 999 * n / 1000, und das Ergebnis wird immer noch O (log n) sein. Aber es gibt keinen Schaden bei der Suche nach n / 2 zuerst.

3) Wie werden wir das Problem so reduzieren? Nun, wenn wir diskontieren können / entfernen m Elemente von Anfang an von einem Array oder das andere als kleiner als die k-te am kleinsten, dann können wir die (km) -te kleinste Element des resultierenden Paar von Anordnungen finden, und es wird die kte kleinste der ursprünglichen Arrays.

4) Schließlich wird die Durchbruch Beobachtung ist, dass, wenn das m-te kleinste Element des Arrays A ist kleiner als das m-te kleinste Element des Arrays B, dann ist das m-te Element von A kann unmöglich die (2m sein) -te kleinstes Element des beide Arrays kombiniert. Es ist kleiner als die (oder gleichwertig: Ich bin nicht sicher, ob „keine Wiederholungen“ bedeutet „keine Wiederholungen in jeder Datenbank“ oder „keine Wiederholungen zwischen den Datenbanken kombiniert“), da es höchstens 2 * (m- 1) Elemente streng kleiner, als es in beiden Arrays kombiniert.

Wenn ich einen Fehler gemacht habe, der Rest Codierung. Mit einem kleinen zusätzlichen Argument-Konto für die off-by-1, wenn k ungerade ist, ist diese Lösung tatsächlich O (log k), die O (log n) Da k <= 2 * n.

Answer 2

Ich sah dieses Problem auf einer Eignungsprüfung nicht lange her, und es riecht wie ein Hausaufgabe Problem. Ich werde daher nur zwei Vorschläge machen:

• Studie binäre Suche, mit besonderer Aufmerksamkeit auf die genaue Art der Schleifeninvarianten. Jon Bentley Buch Programmierung Pearls hat eine gute Erklärung

• Versuchen Sie, die Invarianten für binäre Suche zu verallgemeinern.

• Zeichnen Sie ein Bild mit verschiedenen Sonderfällen:

  • Jede Zahl in DB1 ist kleiner als jede Zahl in DB2
  • Vice versa
  • DB1 gleich DB2
  • Jede Zahl in DB2 ist zweimal die entsprechende Zahl in DB1

Dies ist ein ziemlich schwieriges Problem; Sie werden es leichter haben, wenn Sie gerade einen Beweis für die Richtigkeit gehen.

Answer 3

Tipp:

• Beobachten Sie Ihre "Datenbanken" sind wirklich zwei Arrays sortiert.
• Nehmen Sie Elemente von „Mitte“ der Arrays und sie vergleichen. Das Ergebnis des Vergleichs könnten Sie ermöglichen, zu „ausschließen“, einen Teil.