Finding min/max-Fenster in bewegter O (log (n))

Question

Ich habe diese Schulaufgabe, wo ich eine max/min-Finder von einem sich bewegenden Fenster in O (log (n)) zu erzeugen. Die Zuweisung gibt einen Hinweis zur Verwendung der Java-Klasse java.util.TreeMap oder Warteschlangen in der Implementierung. Bis jetzt konnte ich nur Arbeitscode erstellen, der in O (n) mit Warteschlangen funktioniert. Under ist was ich bisher mit treeMap gemacht habe, aber ich habe Probleme die treeMap Klasse zu verstehen. Ich finde einfach nicht die richtigen Werkzeuge zu benutzen. Jetzt entfernt es den größten Wert, nicht den frühesten. Ich habe versucht, die Werte auch mit Indizes zu paaren, aber dann konnte ich die Werte nicht vergleichen, um den größten Wert zu finden.

Wenn mich jemand mit dieser Sache vorwärts schubsen könnte, würde ich mich freuen.

Answer 1

Haben Sie die TreeMap Dokumentation read?

Eine rot-schwarze baumbasierte NavigableMap-Implementierung. Die Map wird nach der natürlichen Reihenfolge ihrer Schlüssel sortiert, oder nach einem Komparator, der bei der Erstellung der Map zur Verfügung gestellt wird, abhängig davon, welcher Konstruktor verwendet wird.

Diese Implementierung bietet garantierte log (n) Zeitkosten für die containsKey erhalten, setzen und Operationen entfernen. Algorithmen sind Anpassungen von denen in Cormen, Leiserson und Rivest Einführung in Algorithmen.

So ist es eine sortierte Datenstruktur. Obwohl es nicht besagt, können Sie wahrscheinlich davon ausgehen, dass firstKey und lastKey entweder konstante Zeit oder O (log N) sind, also rufen Sie die vier von put, firstKey, und remove geben Sie O (log N) gebunden.

Damit dies funktioniert, müssen Sie den Konstruktor der Treemap einen Hinweis, wie die Schlüssel sortiert sind zu geben. Sie haben hier einen kleinen Unterschied zwischen Scala, wo Sie nach einem impliziten Konvertierungsparameter A => Ordered[A] fragen, und dem TreeMap Konstruktor (der diesen Parameter nicht kennt), also "die natürliche Reihenfolge seiner Schlüssel verwenden" oder ist in Ihrem Fall möglicherweise nicht korrekt.

Wenn Sie sicherstellen möchten, dass die Schlüssel korrekt sortiert sind, sollten Sie entweder sicherstellen, dass A <: Comparable, oder geben Sie eine explizite Comparator.

Da Sie den gleichen Wert wie Schlüssel und Wert speichern, und Sie nie den Wert verwenden, können Sie es auch eine TreeMap[A, Unit], oder in der Tat eine TreeSet machen. Sie könnten auch die java.util.TreeMap für eine ordnungsgemäße Scala-Sammlung, wie collection.mutable.SortedSet tauschen. Dies stellt die Bestellung über eine Instanz von Ordering[A] (eine sogenannte Typklasse) sicher. Es hat die gleichen Methoden firstKey und lastKey.

---

Hinweis: Um den ältesten Wert wie die Fenster Folien zu entfernen, es ist nichts falsch mit einer zweiten Datenstruktur beibehalten wird, die ein schnelle Hinzufügen und Entfernen des ersten oder letzten Elements. Ihre Frage erwähnt auch diese Datenstruktur.