Es ist ein interessantes Puzzle, dem ich begegnet bin, nach dem wir bei einem Array den Ninja-Index finden müssen.
Ein Ninja-Index wird durch diese Regeln definiert:
Ein Index K, so dass alle Elemente mit kleineren Indizes Werte kleiner oder gleich A [K] haben und alle Elemente mit größeren Indizes Werte größer oder gleich A [K] haben.
Betrachten Sie zum Beispiel:
A[0]=4, A[1]=2, A[2]=2, A[3]=3, A[4]=1, A[5]=4, A[6]=7, A[7]=8, A[8]=6, A[9]=9.
In diesem Fall ist 5 ein Ninja-Index, da A [r] & lt; = A [5] für r = [0, k] und A [5] & lt; = A [r] r = [ k, n].
Welchen Algorithmus sollen wir befolgen, um ihn in O (n) zu finden? Ich habe bereits eine Brute-Force-O (n ^ 2) -Lösung.
BEARBEITEN: Es kann mehr als einen Ninja-Index geben, aber wir müssen den ersten finden. Und falls es keine NI gibt, werden wir -1 zurückgeben.
Berechnen Sie Mindestwerte für alle Suffixe des Arrays und Maximalwerte für alle Präfixe. Mit diesen Daten kann jedes Element in O (1) auf Ninja überprüft werden.
Dieser geradlinige Java-Code berechnet den Index ganz links mit der Eigenschaft "Alle Elemente sind nicht kleiner":
%Vor%Fast derselbe Code berechnet den Index ganz links mit der Eigenschaft "Alle Elemente links sind nicht größer":
%Vor%Wenn die Ergebnisse gleich sind, wird der Ninja-Index ganz links gefunden.
Tags und Links algorithm language-agnostic arrays