Daten, die Struktur zu finden, median

Dies ist eine interview-Frage. Entwerfen Sie eine Klasse, die speichert Ganzzahlen und bietet zwei Operationen:

void insert(int k) 
int getMedian()

Ich denke, dass ich verwenden können, BST, so dass insert O(logN) und getMedian O(logN) (für getMedian sollte ich hinzufügen-die Anzahl der rechts - /Kinder für jeden Knoten).

Nun Frage ich mich, ob dies ist die die meisten effiziente Lösung und es gibt keine bessere.

  • Mit Ihrer Regelung, die Sie verbessern können getMedian zu O(1): schauen Sie mal nach, nach jedem einfügen (die nicht Schaden, um die Komplexität) und den Wert speichern.
  • Für eine alternative Struktur, denken, priority queueS.
  • Könnten Sie bitte näher erläutern, wie Sie zu verbessern getMedian O(1)?
  • Ich meine, dass Ihre Daten-Struktur haben würde, die Daten Mitglied int currentMedian;. Sofort nach dem einfügen eines Elements in Ihre BST, finden die neuen median, und speichern diesen Wert in currentMedian vor der Rückkehr von insert. Dann können Sie implementieren int getMedian() { return currentMedian; }, die O(1).
  • Weiter nachdenken, können Sie wahrscheinlich etwas zu tun mit einer skip-Liste zu. Einfügungen, die in rechnen/amortisieren O(log(n)), und Sie können verfolgen, die median Knoten (und ob die Anzahl der Elemente gerade oder ungerade ist). Dann jedes mal, wenn Sie einfügen, brauchen Sie nur, um zu überprüfen, ob Sie den median einen Schritt nach Links oder rechts, abhängig davon, ob Sie Bild auf das Links oder rechts von der alten median und ob die neue Größe gerade oder ungerade ist.
InformationsquelleAutor Michael | 2012-07-06
  1. 24

    Können Sie 2 Haufen, die wir als Left und Right.

    Left ist ein Max-Heap.

    Right ist ein Min-Heap.

    Die Insertion erfolgt über:

    • Wenn das neue element x ist kleiner als die Wurzel der Left dann fügen wir x zu Left.
    • Sonst fügen wir x zu Right.
    • Wenn nach dem einsetzen Left hat die Anzahl der Elemente, die größer als 1 ist von der Anzahl der Elemente von Right, dann nennen wir Extrahieren-Max Left und legen Sie es auf Right.
    • Anderes, wenn nach dem einsetzen Right hat die Anzahl der Elemente, die größer ist als die Anzahl der Elemente von Left, dann rufen Sie Extract-Min auf Right und legen Sie es auf Left.

    Der median ist immer die Wurzel von Left.

    Also die insertion erfolgt in O(lg n) Zeit und immer den median erfolgt in O(1) Zeit.

    • Richtig. Hier ist die Java-Implementierung für Sie: gist.github.com/3675434
    • Toll, meine cpp-Implementierung: gist.github.com/jonnyhsy/7ec9546a3622cf575b82
    • Zu finden ist der Median, legen Sie die zahlen, die Sie gegeben sind in Ordnung finden, und die mittlere Zahl. Beispiel: finde den Median von {13, 23, 11, 16, 15, 10, 26}. Die mittlere Zahl ist 15, also der median ist der 15. (Wenn es zwei mittleren zahlen, Sie Mitteln.) Was ist mit dem Fall der 2 mittleren zahlen ???
    • aber die Sortierung nimmt Sie "n log n" anstelle von "log n".
    • Wenn jemand braucht eine Umsetzung, die auch ermöglicht das entfernen, ich habe erweitert die Lösung, verbunden durch @Amit gist.github.com/JernejJerin/a26276d2289878bd7744
    • könnten Sie bitte kurz erläutern, wie Ihr zum entfernen funktioniert?
    • Die Logik geht so. Zunächst müssen wir überprüfen, ob die Zahl, die wir entfernen wollen, ist größer als das root-element der max-heap. Wenn es ist, dann müssen wir versuchen, Sie zu entfernen aus dem min-heap, sonst entfernen wir von max-Heaps. Beachten Sie, dass min-und max-Heaps implementiert werden, wie PriorityQueue, was bedeutet, dass Entfernung von spezifiziertem Objekt erfolgt in linearer Zeit. Wenn die deinstallation erfolgreich ist, müssen wir überprüfen für die Anzahl der Elemente im heap und zu beheben.
    • Vielen Dank für die Klarstellung. So, das entfernen ist O(n). 🙂
    • Die Idee ist richtig, aber eine kleine Frage: ist die vorgeschlagene Lösung geht von einer geraden Anzahl von zahlen. Die mathematische definition der median deckt auch den Fall von ungerade Anzahl von zahlen. Aus Wikipedia: Wenn es eine gerade Anzahl von Beobachtungen, dann gibt es keinen einzigen mittleren Wert; der median ist dann in der Regel definiert als der Mittelwert der beiden mittleren Werte (en.wikipedia.org/wiki/Median)

    InformationsquelleAutor Avi Cohen
  2. 3

    Sehen diese Stack Overflow Frage für eine Lösung, umfasst zwei Haufen.

    InformationsquelleAutor user448810
  3. 1

    Würde es schlug ein array von Ganzzahlen, die Hexe führt eine Sortierung beim einfügen mal mit einem sort-Algorithmus speziell für integer - (http://en.wikipedia.org/wiki/Sorting_algorithm) wenn Sie wählen Sie Ihre Kandidaten unter O < O(log(n)) und ein array verwenden, dann getMedian würde der index die Hälfte der Größe wäre O(1), Nein? Es scheint mir möglich zu tun, besser als log(n) + log(n).

    Plus, indem Sie ein wenig flexibler können Sie Ihre Leistung verbessern, indem Sie Ihr sort-Algorithmus nach den Eigenschaften Ihrer Eingabe (die Eingabe fast sortiert oder nicht sortiert ...).

    Ich bin ziemlich Autodidakt in der informatik, aber das ist die Art, wie ich es tun würde: einfacher ist besser.

    • Für große Datenmengen würde dies leiden unter der Tatsache, dass insert ist O(n), aber wenn die Anzahl der gespeicherten Werte ist klein, dies ist wahrscheinlich der beste Weg.
    • ja, es war versteckt in den Notizen 🙂 (ich hoffte, niemand würde es bemerken). In der echten Codierung, die beste Umsetzung ist kontextabhängig immer noch ^^. Also ich sehe das theorical Fragen der beste Umsetzung wie der Versuch zu sagen, die mindestens eine Funktion in der form einer einfachen Nummer, wenn Sie Ihre Funktion eingestellt.
    InformationsquelleAutor user1458574
  4. 1

    Könntest du überlegen, ein self-balancing tree, auch. Wenn der Baum ist vollständig ausgeglichen, dann wird der root-Knoten ist median. Sagen, der Baum ist eine Ebene tiefer an einem Ende. Dann, Sie müssen nur wissen, wie viele Knoten gibt es in den tieferen Seite auf, wählen Sie den richtigen median.

    • Angenommen, Ihre maximal-ausgeglichene Baum hat eine ungerade Anzahl von Knoten, dann ist der median der Mittelwert der beiden Werte. Einer dieser Werte ist der root-Knoten, und der andere ist begraben (log n) Ebenen tief in den Baum, da es entweder den linken Knoten des rechten teilbaums oder anderen rechten Knoten des linken teilbaums. So dass Sie brauchen, um die Strecke etwas mehr als nur den root-Knoten und Teilbaum Größen, um den Zugang der median in O(1), sondern die Wurzel allein reicht für O(log n).
    • Könnten Sie bitte geben Sie einige Beispiele von dem Fall, der median ist der Durchschnitt der "weitesten Links liegende Knoten des rechten teilbaums und root"? Jede Probe, die ich versuchen, median Durchschnitt von rechten Knoten des linken teilbaums und root!
    • betrachten Sie einen Baum, bestehend aus zwei Knoten: die Wurzel, und seine Rechte Kind. Dann das Rechte Kind ist der ganz linken Knoten des rechten teilbaums, und der median ist der Mittelwert, der mit der Wurzel.
    InformationsquelleAutor grdvnl
Schreibe einen Kommentar