Ich habe Schwierigkeiten, einen Algorithmus mit O (n) Runeneffizienz zu finden.
Bei einem Array in der Größe n enthält das Array beispielsweise ganze Zahlen. Ich muss wissen, welche Array-Zelle (kann sich als Diagrammleiste vorstellen) auf welche Zelle schaut.
Formal: lookingAtIndex(i) = max { -1} U {j | arr[j] > arr[i], j<i} , wobei -1 für die y-Achse steht.
Bearbeiten : Was ist der erste Balken, der höher ist als der aktuelle Balken, in dem sich im befindet? Wenn es nicht einen gibt, ist seine Y-Achse Beispiel, mit Array zur Verfügung gestellt: 7,3,5,2,1,9 ..
Dann schaut 7 auf y-Achse, 3 schaut auf 7, 5 schaut auf 7, 2 auf 5, 1 auf 2 und 9 auf y-Achse.
Ich bin irgendwie verloren, alles, was ich tue, bleibe ich in O (nLogn). Es ist kein vollständiger Sortieralgorithmus, daher ist es möglich, dies mit O (n) zu tun. Drucken der Ergebnisse ist möglich, während Sie laufen, keine Notwendigkeit, Informationen bis zum Ende zu speichern.
Sie können es mit einem einfachen Stapel machen.
%Vor%Zum Beispiel mit dem Array [7,3,5,2,1,9]
%Vor%Beachten Sie, dass jede Zahl auf den Stapel geschoben wird und jede Zahl nur einmal aus dem Stapel entnommen werden kann, sodass die Anzahl der Stapeloperationen höchstens 2N beträgt und der gesamte Algorithmus O (n) ist.
Ich gehe mit einer linearen Lösung voran, mit einem großen Faktor voraus. Also ich denke, es ist vielleicht nicht die beste Lösung.
Hier ist die Sache. Lassen Sie das Eingabearray von Ganzzahlen I der Länge n aufrufen. Sei M die größte Zahl in I , gefunden in O(n) . Ich nehme zuerst an, dass der minimale Wert in I 0 ist; Wenn nicht, wird durch das Subtrahieren des Min-Werts die Lösung nicht geändert, und M ist im allgemeinen Fall max(I)-min(I) .
Erstellen Sie ein Array T der Länge m , wobei alle Elemente auf -1 gesetzt sind. Dieses Array ist die Speicherung der Indizes des "gesehen" -Balkens für jede mögliche ganze Zahl in I ; Initialisierung ist -1, Index eines virtuellen Links am weitesten links.
Erstellen Sie auch das Array S als Ausgabe-Array o die Indizes der "betrachteten" Balken.
Nun wird für jedes Element e in I mit dem Index i im Array der Balken betrachtet, dessen Index genau T[e] ist. Also S[i] = T[e] . Setzen Sie dann alle Elemente T[0..e] mit dem Wert i .
Am Ende der Schleife wird S mit den Indizes der "betrachteten" Balken gefüllt; Es ist einfach, den Wert dieser Balken zurück zu bekommen.
Wie Sie sehen, ist die Gesamtkomplexität O(M*n) , also ist die Komplexität linear mit der Länge von I . Es ist möglicherweise nicht sehr effizient wegen des Faktors M , wie ich vorher sagte (jede Verbesserung ist willkommen).
BEARBEITEN
Bevorzugen Sie die Lösung von user3386109 , meine ist im Vergleich peinlich.
Nehmen wir an, wir haben ein Array, das endet mit: ... A - B,
und lookingAtIndex (A) = X, und lasst uns das Ergebnis für B finden: wenn A & gt; B dann ist es A, sonst können alle Indizes zwischen A und lookingAtIndex (A) keine gute Antwort sein, da sie kleiner als A sind. wenn lookingAtIndex (A) & gt; B dann ist es die Antwort, sonst schaue auf LookingAtIndex (lookingAtIndex (A)) etc ...
Aber Sie werden einen Weg brauchen, um die Balken jedes Indexes zu speichern. Ich denke, die Idee des Stacks von user3386109 ist eine sehr gute Implementierung, und Sie müssen nur die benötigten Werte speichern