Suchen Sie die erste Zahl, die größer ist als eine gegebene in einer unsortierten Sequenz.

Question

Gegeben eine Folge von positiven ganzen Zahlen und einer ganzen Zahl M, geben Sie die erste Zahl in der Folge zurück, die größer als M ist (oder -1, falls nicht vorhanden) .

Beispiel: sequence = [2, 50, 8, 9, 1], M = 3 -> 50 return =

O (log n) für jede Abfrage erforderlich ist (nach der Vorverarbeitung).

Ich habe von BSTs gedacht, aber eine aufsteigende Folge gegeben i nur einen langen Weg bekommen würde, die mir nicht geben würde O (log n) Zeit ...

EDIT: Gebrauchte Struktur sollte auch leicht zu ändern, dh es sollte möglich sein, gefundenes Element durch das gegebene zu ersetzen und die Suche nach einem anderen M zu wiederholen (alles - außer der Vorverarbeitung - O (logn)). Und natürlich wäre es schön, wenn ich "first greater" zu "first small" ändern könnte und nicht zu viel im Algorithmus ändern müsste. Und wenn es hilft, können wir annehmen, dass alle Zahlen positiv sind und es keine Wiederholungen gibt.

Answer 1

ein zweites Array erstellen (lass es seine aux), wobei für jedes Element i: aux[i] = max { arr[0],arr[1], ... ,arr[i]} (das Maximum aller Elemente mit dem Index in dem ursprünglichen j <= i Array).

Es ist leicht zu sehen, dass dieses Array nach der Art sortiert ist, und eine einfache binary search on aux wird den benötigten Index ergeben. (Es ist leicht, mit einer binären Suche das erste Element zu erhalten, das größer als das angeforderte Element ist, wenn das Element nicht existiert).

Zeit Komplexität ist O(n) Vorverarbeitung (nur einmal getan) und O(logn) pro Abfrage.