Finden Sie Tripletts in besser als lineare Zeit, so dass A [n-1]> = A [n] <= A [n + 1]

Question

Eine Reihe von Zahlen wurde in einem Interview gegeben, so dass A[0] >= A[1] und A[N-1] >= A[N-2]. Ich wurde gebeten, mindestens ein Triplett zu finden, so dass A[n-1] >= A[n] <= A[n+1].

Ich versuchte in Iterationen zu lösen. Interviewer erwartet besser als lineare Zeitlösung. Wie soll ich diese Frage angehen?

Beispiel: 9 8 5 4 3 2 6 7

Antwort: 3 2 6

Answer 1

Linear konnte man nur tun, indem sie durch den Satz laufen, zu vergleichen sie alle.

Sie könnten auch die Steigung der ersten beiden überprüfen, dann eine Art binärer Chop/in der Reihenfolge Traversal vergleichen Paare, bis Sie eine der gegenüberliegenden Steigung finden. Das würde sich auf einen besser als n Zeitpunkt amortisieren, denke ich, obwohl es nicht garantiert ist.

edit: gerade realisiert, was Ihre Bestellung bedeutete. Die Binär-Chop-Methode wird dies garantiert in <n Zeit, da es garantiert ist ein Punkt der Änderung (vorausgesetzt, dass Ihre N-1, N-2 sind die letzten zwei Elemente der Liste). Dies bedeutet, dass Sie es nur finden müssen/einer von ihnen, in welchem ​​Fall binäre hacken es um log(n)

Answer 2

tun wir dies in O(logn) Zeit lösen können aka divide & erobern werden. binäre Suche. Besser als lineare Zeit. Also müssen wir ein Triplett finden, so dass A[n-1] >= A[n] <= A[n+1].

Zuerst finden Sie die Mitte des angegebenen Arrays. Wenn Mitte kleiner als links und größer als rechts ist. Dann komm zurück, das ist deine Antwort. Übrigens wäre dies ein Grundfall in Ihrer Rekursion. Auch wenn len(arr) < 3 dann auch zurückkommt. ein anderer Basecase.

Jetzt kommt die Rekursion Szenarien. Um zu rekrutieren, müssten wir weiter rechts inspizieren. Falls if mid größer als das Element auf der linken Seite ist, sollten Sie daher davon ausgehen, dass Sie als Teilproblem links vom Array beginnen und mit diesem neuen Array rekursiv arbeiten. das heißt in greifbare Begriffe an dieser Stelle würden wir ...2... mit Index n wird 6. Also nach links bewegen wir sehen, ob das Element links von 2 das Triplett abgeschlossen ist.

Andernfalls, wenn mid größer ist als das Element auf seinem rechten Subarray, dann betrachten Sie mid + 1 nach rechts des Arrays als ein Teilproblem und recurse.

---

Mehr Theorie: Die oben sollte ausreichend sein, um das Problem zu verstehen, aber lesen Sie weiter. Das Problem besteht im Wesentlichen darin, lokale Minima in einer gegebenen Menge von Elementen zu finden. Eine Zahl im Array heißt lokale Minima, wenn sie kleiner als ihre linke und rechte Zahl ist, was genau auf A[n-1] >= A[n] <= A[n+1] hinausläuft.

Ein gegebenes Array, so dass seine ersten 2 Elemente abnehmen und die letzten 2 Elemente ein lokales Minimum haben. Warum das? Lasst uns dies durch Verneinung beweisen. Wenn die ersten beiden Zahlen abnehmen und keine lokalen Minima vorhanden sind, bedeutet dies, dass die dritte Zahl kleiner als die zweite Zahl ist. andernfalls wäre die zweite Zahl lokale Minima gewesen. Nach der gleichen Logik muss die 4. Nummer kleiner als die 3. Nummer sein und so weiter und so fort. Also müssen die Zahlen im Array in absteigender Reihenfolge sein.Die verletzt die Beschränkung der letzten zwei Zahlen in aufsteigender Reihenfolge. Dies beweist durch die Negation, dass es ein lokales Minimum geben muss.

Die obige Theorie schlägt einen linearen Ansatz O(n) vor, aber wir können definitiv besser machen. Aber die Theorie gibt uns definitiv eine andere Perspektive auf das Problem.

---

Code: Hier Python-Code (FYI - wurde in Stackoverflow Texteditor freihändig eingegeben haben, es könnte misbheave).

def local_minima(arr, start, end): 
    mid = (start+end)/2 

    if mid-2 < 0 and mid+1 >= len(arr): 
     return -1; 

    if arr[mid-2] > arr[mid-1] and arr[mid-1] < arr[mid]: #found it! 
     return mid-1; 

    if arr[mid-1] > arr[mid-2]: 
     return local_minima(arr, start, mid); 
    else: 
     return local_minima(arr, mid, end); 

Bitte beachte, dass ich den Index des n gerade zurück. Um das Triple auszudrucken, tun Sie einfach -1 und +1 zum zurückgegebenen Index. source

Answer 3

Es klingt wie das, was Sie fragen, ist dies:

Sie eine Folge von Zahlen haben. Es beginnt abzunehmen und nimmt weiter bis Element n ab, dann beginnt es bis zum Ende der Sequenz anzusteigen. Suche n.

Dies ist eine (nicht optimale) Lösung in linearer Zeit:

for (i = 1; i < length(A) - 1; i++) 
{ 
    if ((A[i-1] >= A[i]) && (A[i] <= A[i+1])) 
     return i; 
} 

als lineare Zeit besser zu machen, müssen Sie die Informationen verwenden, die Sie aus der Tatsache erhalten, dass die Serie erhöht sinken dann.

Betrachten Sie den Unterschied zwischen A[i] und A[i+1]. Wenn A[i] > A[i+1], dann n > i, da die Werte immer noch sinken. Wenn A[i] <= A[i+1], dann n <= i, da die Werte jetzt zunehmen. In diesem Fall müssen Sie den Unterschied zwischen A[i-1] und A[i] überprüfen.

Dies ist eine Lösung in Protokollzeit:

int boundUpper = length(A) - 1; 
int boundLower = 1; 
int i = (boundUpper + boundLower)/2; //initial estimate 

while (true) 
{ 
    if (A[i] > A[i+1]) 
     boundLower = i + 1; 
    else if (A[i-1] >= A[i]) 
     return i; 
    else 
     boundUpper = i; 

    i = (boundLower + boundUpper)/2; 
} 

ich es Ihnen überlassen würde in der notwendigen Fehlerprüfung im Fall hinzufügen, dass A kein Element der Kriterien erfüllt hat.